Submission #1194719
Source Code Expand
// In the name of God #include <iostream> #include <algorithm> #include <fstream> #include <vector> #include <deque> #include <assert.h> #include <queue> #include <stack> #include <set> #include <map> #include <stdio.h> #include <string.h> #include <utility> #include <math.h> #include <bitset> #include <iomanip> #include <complex> using namespace std; #define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i) #define debug(...) fprintf(stderr, __VA_ARGS__) #define mp make_pair #define x first #define y second #define pb push_back #define SZ(x) (int((x).size())) #define ALL(x) (x).begin(), (x).end() template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template<typename T> inline bool smin(T &a, const T &b) { return a > b ? a = b : a; } template<typename T> inline bool smax(T &a, const T &b) { return a < b ? a = b : a; } typedef long long LL; const int N = (int) 1e6 + 6, mod = (int) 0; set<int> all[N]; int qv[N], qd[N], qc[N], q[N * 10], seen[N], res[N]; vector<int> adj[N]; int main() { ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; memset(seen, -1, sizeof seen); for (int j = 0; j < m; ++j) { int u, v; cin >> u >> v; --u, --v; adj[u].push_back(v); adj[v].push_back(u); } int qn; cin >> qn; for (int j = 0; j < qn; ++j) { cin >> qv[j] >> qd[j] >> qc[j]; --qv[j]; } for (int j = qn - 1; j >= 0; --j) { int h = 0, t = 0; if (seen[qv[j]] < qd[j]) { seen[qv[j]] = qd[j]; q[t++] = qv[j]; } while (h != t) { int v = q[h++]; if (!res[v]) { res[v] = qc[j]; } if (seen[v] <= 0) { continue; } for (int u : adj[v]) { if (seen[u] < seen[v] - 1) { seen[u] = seen[v] - 1; q[t++] = u; } } } } for (int j = 0; j < n; ++j) cout << res[j] << '\n'; }
Submission Info
Submission Time | |
---|---|
Task | B - Splatter Painting |
User | Reyna |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1998 Byte |
Status | AC |
Exec Time | 109 ms |
Memory | 88056 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 | 29 ms | 84096 KB |
00_example_02.txt | AC | 29 ms | 84096 KB |
10_01.txt | AC | 29 ms | 84096 KB |
10_02.txt | AC | 29 ms | 84096 KB |
10_03.txt | AC | 29 ms | 84096 KB |
10_04.txt | AC | 29 ms | 84096 KB |
10_05.txt | AC | 29 ms | 84096 KB |
10_06.txt | AC | 29 ms | 84096 KB |
10_07.txt | AC | 29 ms | 84096 KB |
10_08.txt | AC | 31 ms | 84224 KB |
10_09.txt | AC | 31 ms | 84224 KB |
10_10.txt | AC | 30 ms | 84224 KB |
10_11.txt | AC | 31 ms | 84224 KB |
10_12.txt | AC | 31 ms | 84224 KB |
10_13.txt | AC | 30 ms | 84224 KB |
10_14.txt | AC | 30 ms | 84224 KB |
10_15.txt | AC | 30 ms | 84224 KB |
10_16.txt | AC | 30 ms | 84224 KB |
10_17.txt | AC | 30 ms | 84224 KB |
20_01.txt | AC | 108 ms | 87296 KB |
20_02.txt | AC | 108 ms | 87296 KB |
20_03.txt | AC | 109 ms | 87296 KB |
20_04.txt | AC | 40 ms | 84864 KB |
20_05.txt | AC | 31 ms | 84096 KB |
20_06.txt | AC | 36 ms | 84352 KB |
20_07.txt | AC | 31 ms | 84096 KB |
20_08.txt | AC | 45 ms | 84224 KB |
20_09.txt | AC | 30 ms | 84096 KB |
20_10.txt | AC | 45 ms | 84096 KB |
20_11.txt | AC | 50 ms | 84224 KB |
20_12.txt | AC | 72 ms | 87296 KB |
20_13.txt | AC | 92 ms | 87424 KB |
20_14.txt | AC | 98 ms | 87424 KB |
20_15.txt | AC | 87 ms | 87800 KB |
20_16.txt | AC | 89 ms | 88056 KB |