Submission #1372349
Source Code Expand
#include <iostream> #include <vector> #include <list> #include <queue> int main() { unsigned N; std::cin >> N; std::vector<std::vector<unsigned>> G(N); std::vector<std::vector<unsigned>> G0(N); for (unsigned i = 0; i < N - 1; ++i) { unsigned x, y; std::cin >> x >> y; --x; --y; G0[x].push_back(y); G0[y].push_back(x); } unsigned K; std::cin >> K; std::vector<std::pair<int, int>> color(N); for (auto &i : color) { i.first = std::numeric_limits<int>::min() / 2; i.second = std::numeric_limits<int>::max() / 2; } for (unsigned i = 0; i < K; ++i) { unsigned x, y; std::cin >> x >> y; --x; color[x] = std::make_pair(y, y); } std::queue<unsigned> queue; std::vector<unsigned> order(N); std::vector<bool> used(N, false); queue.push(0); unsigned o = 0; while (!queue.empty()) { auto x = queue.front(); used[x] = true; order[o++] = x; queue.pop(); for (auto &e : G0[x]) { if (!used[e]) { queue.push(e); } } } for (unsigned i = 0; i < N; ++i) { for (auto &e : G0[i]) { if (order[i] < order[e]) { G[i].push_back(e); } } } std::vector<int> even_odd(N, -1); for (unsigned t = 0; t < N; ++t) { auto i = order[t]; if (color[i].first == color[i].second) { if (even_odd[i] < 0) { even_odd[i] = color[i].first % 2; } else { if (even_odd[i] != color[i].first % 2) { std::cout << "No"; return 0; } } } int x = color[i].first % 2 ? 0 : 1; for (auto e : G[i]) { if (even_odd[i] < 0) { even_odd[i] = x; } else { if (even_odd[i] == even_odd[e]) { std::cout << "No"; return 0; } } } } for (unsigned t = N; t-- > 0;) { auto i = order[t]; for (auto e : G[i]) { color[i].first = std::max(color[i].first, color[e].first - 1); color[i].second = std::min(color[i].second, color[e].second + 1); } if (color[i].first % 2 != even_odd[i]) { ++color[i].first; } if (color[i].second % 2 != even_odd[i]) { --color[i].second; } if (color[i].first > color[i].second) { std::cout << "No" << std::endl; return 0; } } std::cout << "Yes" << std::endl; for (unsigned t = 0; t < N; ++t) { auto i = order[t]; for (auto e : G[i]) { if (color[e].first <= color[i].first - 1) { color[e].first = color[i].first - 1; } else { color[e].first = color[i].first + 1; } } } for (unsigned i = 0; i < N; ++i) { std::cout << color[i].first << std::endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Integers on a Tree |
User | ytsmiling |
Language | C++14 (Clang 3.8.0) |
Score | 0 |
Code Size | 2762 Byte |
Status | WA |
Exec Time | 546 ms |
Memory | 12800 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 | WA | 242 ms | 11264 KB |
binary_02.txt | AC | 177 ms | 11264 KB |
hand_01.txt | AC | 1 ms | 256 KB |
hand_02.txt | AC | 1 ms | 256 KB |
hand_03.txt | AC | 1 ms | 256 KB |
kary_01.txt | AC | 172 ms | 11264 KB |
kary_02.txt | WA | 169 ms | 10752 KB |
kary_03.txt | AC | 169 ms | 10752 KB |
line_01.txt | AC | 201 ms | 12800 KB |
line_02.txt | WA | 171 ms | 12800 KB |
line_03.txt | WA | 171 ms | 12800 KB |
line_04.txt | WA | 203 ms | 12800 KB |
line_05.txt | AC | 171 ms | 12800 KB |
line_06.txt | AC | 203 ms | 12800 KB |
random0_01.txt | AC | 260 ms | 11648 KB |
random1_01.txt | WA | 186 ms | 11648 KB |
random1_02.txt | WA | 193 ms | 11648 KB |
random1_03.txt | WA | 201 ms | 11648 KB |
random1_04.txt | WA | 269 ms | 11648 KB |
random1_05.txt | WA | 184 ms | 11648 KB |
random1_06.txt | WA | 185 ms | 11648 KB |
random1_07.txt | WA | 192 ms | 11648 KB |
random1_08.txt | AC | 546 ms | 12416 KB |
random2_01.txt | AC | 184 ms | 11648 KB |
random2_02.txt | AC | 185 ms | 11648 KB |
random2_03.txt | AC | 186 ms | 11648 KB |
random2_04.txt | AC | 192 ms | 11648 KB |
random2_05.txt | AC | 262 ms | 11648 KB |
random2_06.txt | AC | 348 ms | 11648 KB |
random3_01.txt | AC | 184 ms | 11648 KB |
random3_02.txt | AC | 265 ms | 11648 KB |
random4_01.txt | WA | 185 ms | 11648 KB |
random4_02.txt | WA | 187 ms | 11648 KB |
random4_03.txt | WA | 183 ms | 11648 KB |
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
star_01.txt | WA | 214 ms | 11128 KB |
star_02.txt | AC | 214 ms | 11128 KB |