Submission #2097375
Source Code Expand
#include <iostream> #include <sstream> #include <vector> #include <queue> #include <algorithm> #include <set> using namespace std; int n; int k; typedef pair<int,int> P; vector<P> edges[100001]; int l[100001]; int r[100001]; queue<int> que; int INF = 1e9; bool solve() { while(!que.empty()) { int v = que.front(); que.pop(); int nl = l[v] - 1; int nr = r[v] + 1; for(P& p : edges[v]) { if(l[p.first] !=INF && abs(nl - l[p.first]) % 2 == 1) { return false; } if(l[p.first] == INF || l[p.first] < nl || nr < r[p.first]) { //update if(l[p.first] == INF) { l[p.first] = nl; r[p.first] = nr; } l[p.first] = max(l[p.first] , nl); r[p.first] = min(r[p.first] , nr); if(!(l[p.first] <= r[p.first])) return false; que.push(p.first); } } } return true; } int main() { fill(l,l + 100001,INF); fill(r,r + 100001,INF); cin >> n; for(int i = 0;i < n - 1;i++) { int a,b; cin >> a >> b; edges[a].push_back(P{b,0}); edges[b].push_back(P{a,0}); } cin >> k; for(int i = 0;i < k;i++) { int v,p; cin >> v >> p; que.push(v); l[v] = p; r[v] = p; } if(!solve()) { cout << "No" << endl; return 0; } cout << "Yes" << endl; for(int i = 1;i <= n;i++) { //cerr << i << "-" << l[i] << ":" << r[i] << endl; cout << l[i] << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Integers on a Tree |
User | niuez |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1472 Byte |
Status | AC |
Exec Time | 284 ms |
Memory | 8192 KB |
Judge Result
Set Name | sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 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 | 250 ms | 8192 KB |
binary_02.txt | AC | 70 ms | 7296 KB |
hand_01.txt | AC | 3 ms | 3328 KB |
hand_02.txt | AC | 3 ms | 3328 KB |
hand_03.txt | AC | 3 ms | 3328 KB |
kary_01.txt | AC | 68 ms | 7296 KB |
kary_02.txt | AC | 221 ms | 7808 KB |
kary_03.txt | AC | 67 ms | 7040 KB |
line_01.txt | AC | 78 ms | 6528 KB |
line_02.txt | AC | 221 ms | 7168 KB |
line_03.txt | AC | 223 ms | 7168 KB |
line_04.txt | AC | 234 ms | 7296 KB |
line_05.txt | AC | 67 ms | 6528 KB |
line_06.txt | AC | 79 ms | 6528 KB |
random0_01.txt | AC | 99 ms | 7168 KB |
random1_01.txt | AC | 235 ms | 7680 KB |
random1_02.txt | AC | 236 ms | 7808 KB |
random1_03.txt | AC | 241 ms | 7808 KB |
random1_04.txt | AC | 263 ms | 7936 KB |
random1_05.txt | AC | 249 ms | 7680 KB |
random1_06.txt | AC | 236 ms | 7680 KB |
random1_07.txt | AC | 243 ms | 7808 KB |
random1_08.txt | AC | 284 ms | 8064 KB |
random2_01.txt | AC | 72 ms | 7040 KB |
random2_02.txt | AC | 72 ms | 7040 KB |
random2_03.txt | AC | 73 ms | 7040 KB |
random2_04.txt | AC | 76 ms | 7040 KB |
random2_05.txt | AC | 100 ms | 7168 KB |
random2_06.txt | AC | 129 ms | 7424 KB |
random3_01.txt | AC | 75 ms | 7040 KB |
random3_02.txt | AC | 101 ms | 7168 KB |
random4_01.txt | AC | 231 ms | 7680 KB |
random4_02.txt | AC | 230 ms | 7680 KB |
random4_03.txt | AC | 229 ms | 7680 KB |
sample_01.txt | AC | 3 ms | 3328 KB |
sample_02.txt | AC | 3 ms | 3328 KB |
sample_03.txt | AC | 3 ms | 3328 KB |
star_01.txt | AC | 236 ms | 8180 KB |
star_02.txt | AC | 81 ms | 7540 KB |