Submission #1678785
Source Code Expand
#include<bits/stdc++.h> using namespace std; int main(){ int n, m; cin >> n >> m; vector<int> v[n]; for(int i = 0; i < m; ++i){ int a, b; cin >> a >> b; v[--a].push_back(--b); v[b].push_back(a); } int q; cin >> q; int color[q + 1] = {}; int dp[n][11]; for(int i = 0; i < n; ++i){ for(int j = 0; j < 11; ++j) dp[i][j] = q; } for(int i = 0; i < q; ++i){ int v, d, c; cin >> v >> d >> c; color[q - 1 - i] = c; dp[--v][d] = q - 1 - i; } for(int j = 10; j >= 1; --j){ for(int i = 0; i < n; ++i){ dp[i][j - 1] = min(dp[i][j - 1], dp[i][j]); for(int next : v[i]) dp[next][j - 1] = min(dp[next][j - 1], dp[i][j]); } } for(int i = 0; i < n; ++i) cout << color[dp[i][0]] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Splatter Painting |
User | kcvlex |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 751 Byte |
Status | AC |
Exec Time | 340 ms |
Memory | 11128 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 | 7 ms | 384 KB |
10_09.txt | AC | 7 ms | 384 KB |
10_10.txt | AC | 7 ms | 384 KB |
10_11.txt | AC | 7 ms | 384 KB |
10_12.txt | AC | 7 ms | 384 KB |
10_13.txt | AC | 6 ms | 384 KB |
10_14.txt | AC | 5 ms | 384 KB |
10_15.txt | AC | 5 ms | 384 KB |
10_16.txt | AC | 7 ms | 512 KB |
10_17.txt | AC | 7 ms | 512 KB |
20_01.txt | AC | 335 ms | 10496 KB |
20_02.txt | AC | 340 ms | 10496 KB |
20_03.txt | AC | 338 ms | 10496 KB |
20_04.txt | AC | 37 ms | 1408 KB |
20_05.txt | AC | 6 ms | 256 KB |
20_06.txt | AC | 153 ms | 6784 KB |
20_07.txt | AC | 6 ms | 384 KB |
20_08.txt | AC | 46 ms | 640 KB |
20_09.txt | AC | 6 ms | 384 KB |
20_10.txt | AC | 46 ms | 512 KB |
20_11.txt | AC | 61 ms | 768 KB |
20_12.txt | AC | 254 ms | 9472 KB |
20_13.txt | AC | 317 ms | 10112 KB |
20_14.txt | AC | 310 ms | 9984 KB |
20_15.txt | AC | 300 ms | 11000 KB |
20_16.txt | AC | 301 ms | 11128 KB |