Submission #1513476
Source Code Expand
#include <queue> #include <vector> #include <iostream> #include <algorithm> #include <functional> using namespace std; struct state { int pos, val; }; bool operator<(const state& s1, const state& s2) { return s1.val > s2.val; } int N, K, a, b, c[100009], p[100009]; vector<int> g[100009]; int main() { ios::sync_with_stdio(false); cin >> N; for (int i = 0; i < N - 1; i++) { cin >> a >> b; a--, b--; g[a].push_back(b); g[b].push_back(a); } fill(c, c + N, -1); fill(p, p + N, -1); cin >> K; priority_queue<state> que; for (int i = 0; i < K; i++) { cin >> a >> b, c[--a] = b; que.push(state{ a, b }); p[a] = b; } while (!que.empty()) { state u = que.top(); que.pop(); for (int i : g[u.pos]) { if (p[i] == -1 || p[i] > p[u.pos] + 1) { p[i] = p[u.pos] + 1; que.push(state{ i, p[i] }); } } } bool f = true; for (int i = 0; i < N; i++) { if (c[i] != -1 && p[i] != c[i]) f = false; } if (!f) cout << "No" << endl; else { cout << "Yes" << endl; for (int i = 0; i < N; i++) cout << p[i] << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Integers on a Tree |
User | square1001 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1099 Byte |
Status | WA |
Exec Time | 212 ms |
Memory | 8308 KB |
Judge Result
Set Name | sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 800 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | binary_01.txt, binary_02.txt, hand_01.txt, hand_02.txt, hand_03.txt, kary_01.txt, kary_02.txt, kary_03.txt, line_01.txt, line_02.txt, line_03.txt, line_04.txt, line_05.txt, line_06.txt, random0_01.txt, random1_01.txt, random1_02.txt, random1_03.txt, random1_04.txt, random1_05.txt, random1_06.txt, random1_07.txt, random1_08.txt, random2_01.txt, random2_02.txt, random2_03.txt, random2_04.txt, random2_05.txt, random2_06.txt, random3_01.txt, random3_02.txt, random4_01.txt, random4_02.txt, random4_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, star_01.txt, star_02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
binary_01.txt | AC | 194 ms | 7672 KB |
binary_02.txt | AC | 37 ms | 6528 KB |
hand_01.txt | AC | 2 ms | 2560 KB |
hand_02.txt | AC | 2 ms | 2560 KB |
hand_03.txt | AC | 2 ms | 2560 KB |
kary_01.txt | AC | 37 ms | 7164 KB |
kary_02.txt | AC | 185 ms | 7420 KB |
kary_03.txt | AC | 35 ms | 6912 KB |
line_01.txt | AC | 44 ms | 6912 KB |
line_02.txt | AC | 176 ms | 7168 KB |
line_03.txt | AC | 177 ms | 7168 KB |
line_04.txt | AC | 189 ms | 7548 KB |
line_05.txt | AC | 30 ms | 6528 KB |
line_06.txt | AC | 42 ms | 6912 KB |
random0_01.txt | AC | 62 ms | 7164 KB |
random1_01.txt | AC | 193 ms | 7296 KB |
random1_02.txt | AC | 190 ms | 7296 KB |
random1_03.txt | AC | 192 ms | 7424 KB |
random1_04.txt | AC | 204 ms | 7800 KB |
random1_05.txt | AC | 197 ms | 7296 KB |
random1_06.txt | AC | 197 ms | 7296 KB |
random1_07.txt | AC | 194 ms | 7296 KB |
random1_08.txt | AC | 212 ms | 8180 KB |
random2_01.txt | AC | 42 ms | 6656 KB |
random2_02.txt | AC | 41 ms | 6656 KB |
random2_03.txt | AC | 42 ms | 6656 KB |
random2_04.txt | AC | 44 ms | 6656 KB |
random2_05.txt | AC | 54 ms | 7164 KB |
random2_06.txt | AC | 61 ms | 7672 KB |
random3_01.txt | AC | 42 ms | 6656 KB |
random3_02.txt | WA | 203 ms | 7800 KB |
random4_01.txt | AC | 190 ms | 7296 KB |
random4_02.txt | AC | 190 ms | 7296 KB |
random4_03.txt | AC | 191 ms | 7296 KB |
sample_01.txt | AC | 2 ms | 2560 KB |
sample_02.txt | AC | 2 ms | 2560 KB |
sample_03.txt | AC | 2 ms | 2560 KB |
star_01.txt | AC | 190 ms | 8308 KB |
star_02.txt | AC | 41 ms | 8056 KB |