Submission #1520499
Source Code Expand
#include <bits/stdc++.h> using namespace std; using P = pair<int, int>; int dmax; vector<vector<int>> G; vector<vector<int>> color; void bfs(int s, int d, int c) { queue<P> que; que.push({s, d}); while (!que.empty()) { P p = que.front(); que.pop(); int u = p.first, l = p.second; if (color[u][l] >= 0) continue; for (int i = 0; i <= l; i++) { if (color[u][i] == -1) color[u][i] = c; } for (auto&& v : G[u]) que.push({v, l - 1}); } } main() { int N, M; cin >> N >> M; G.resize(N); for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(b); G[b].push_back(a); } int Q; cin >> Q; vector<int> v(Q), d(Q), c(Q); for (int i = 0; i < Q; i++) { cin >> v[i] >> d[i] >> c[i]; v[i]--; dmax = max(dmax, d[i]); } color.assign(N, vector<int>(dmax + 1, -1)); for (int i = Q - 1; i >= 0; i--) { bfs(v[i], d[i], c[i]); } for (int i = 0; i < N; i++) cout << ( (color[i][0] == -1) ? 0 : color[i][0] ) << endl; }
Submission Info
Submission Time | |
---|---|
Task | B - Splatter Painting |
User | hrbt |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1062 Byte |
Status | AC |
Exec Time | 368 ms |
Memory | 16760 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 500 / 500 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt |
Subtask1 | 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt |
All | 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt, 20_01.txt, 20_02.txt, 20_03.txt, 20_04.txt, 20_05.txt, 20_06.txt, 20_07.txt, 20_08.txt, 20_09.txt, 20_10.txt, 20_11.txt, 20_12.txt, 20_13.txt, 20_14.txt, 20_15.txt, 20_16.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 1 ms | 256 KB |
00_example_02.txt | AC | 1 ms | 256 KB |
10_01.txt | AC | 2 ms | 256 KB |
10_02.txt | AC | 1 ms | 256 KB |
10_03.txt | AC | 1 ms | 256 KB |
10_04.txt | AC | 1 ms | 256 KB |
10_05.txt | AC | 2 ms | 256 KB |
10_06.txt | AC | 1 ms | 256 KB |
10_07.txt | AC | 4 ms | 384 KB |
10_08.txt | AC | 8 ms | 512 KB |
10_09.txt | AC | 7 ms | 512 KB |
10_10.txt | AC | 8 ms | 512 KB |
10_11.txt | AC | 8 ms | 512 KB |
10_12.txt | AC | 7 ms | 512 KB |
10_13.txt | AC | 6 ms | 512 KB |
10_14.txt | AC | 5 ms | 512 KB |
10_15.txt | AC | 5 ms | 512 KB |
10_16.txt | AC | 7 ms | 640 KB |
10_17.txt | AC | 7 ms | 512 KB |
20_01.txt | AC | 366 ms | 15616 KB |
20_02.txt | AC | 359 ms | 15616 KB |
20_03.txt | AC | 368 ms | 15616 KB |
20_04.txt | AC | 40 ms | 2060 KB |
20_05.txt | AC | 7 ms | 384 KB |
20_06.txt | AC | 155 ms | 11008 KB |
20_07.txt | AC | 8 ms | 384 KB |
20_08.txt | AC | 63 ms | 1280 KB |
20_09.txt | AC | 7 ms | 384 KB |
20_10.txt | AC | 64 ms | 1152 KB |
20_11.txt | AC | 83 ms | 1664 KB |
20_12.txt | AC | 229 ms | 13440 KB |
20_13.txt | AC | 310 ms | 14848 KB |
20_14.txt | AC | 322 ms | 14592 KB |
20_15.txt | AC | 334 ms | 16760 KB |
20_16.txt | AC | 343 ms | 16760 KB |