Submission #1196162
Source Code Expand
#include<stdio.h> #include<vector> #include<queue> #define rep(i,n)for(int i=0;i<(n);i++) #define MOD 1000000007 #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define EPS (1e-10) using namespace std; typedef long long ll; typedef pair<int, int>P; #define mygc(c) (c)=getchar_unlocked() #define mypc(c) putchar_unlocked(c) void reader(int *x) { int k, m = 0; *x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { *x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; *x = (*x) * 10 + k - '0'; }if (m)(*x) = -(*x); } void reader(int *x, int *y) { reader(x); reader(y); } void reader(int *x, int *y, int *z) { reader(x); reader(y); reader(z); } void writer(int x, char c) { int i, sz = 0, m = 0; char buf[10]; if (x<0)m = 1, x = -x; while (x)buf[sz++] = x % 10, x /= 10; if (!sz)buf[sz++] = 0; if (m)mypc('-'); while (sz--)mypc(buf[sz] + '0'); mypc(c); } vector<int>E[100000]; int d1[100000]; int c1[100000], c2[100000]; int que[100000]; int v[100000], d[100000], c[100000]; int mq[100000]; signed main() { int n, m; reader(&n, &m); rep(i, m) { int a, b; reader(&a, &b); a--; b--; E[a].push_back(b); E[b].push_back(a); } memset(c2, -1, sizeof(c2)); int q; reader(&q); rep(i, q) { reader(&v[i], &d[i], &c[i]); v[i]--; mq[v[i]] = i; } rep(i, q) { int s = 0, g = 0; d1[v[i]] = 0; c1[v[i]] = c[i]; c2[v[i]] = i; if (d1[v[i]] < d[i])que[g++] = v[i]; while (s != g) { int p = que[s++]; int siz = E[p].size(); rep(j, siz) { int u = E[p][j]; if (c2[u] != i) { c1[u] = c[i]; c2[u] = i; d1[u] = d1[p] + 1; if (d1[u] < d[i])que[g++] = u; } } } } rep(i, n)writer(c1[i], '\n'); }
Submission Info
Submission Time | |
---|---|
Task | B - Splatter Painting |
User | autumn_eel |
Language | C++14 (Clang 3.8.0) |
Score | 200 |
Code Size | 1735 Byte |
Status | TLE |
Exec Time | 2107 ms |
Memory | 11256 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 0 / 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 | 6 ms | 4984 KB |
00_example_02.txt | AC | 3 ms | 4352 KB |
10_01.txt | AC | 3 ms | 4352 KB |
10_02.txt | AC | 3 ms | 4352 KB |
10_03.txt | AC | 3 ms | 4352 KB |
10_04.txt | AC | 3 ms | 4352 KB |
10_05.txt | AC | 3 ms | 4352 KB |
10_06.txt | AC | 3 ms | 4352 KB |
10_07.txt | AC | 3 ms | 4352 KB |
10_08.txt | AC | 6 ms | 4480 KB |
10_09.txt | AC | 5 ms | 4480 KB |
10_10.txt | AC | 5 ms | 4480 KB |
10_11.txt | AC | 5 ms | 4480 KB |
10_12.txt | AC | 5 ms | 4480 KB |
10_13.txt | AC | 3 ms | 4480 KB |
10_14.txt | AC | 3 ms | 4480 KB |
10_15.txt | AC | 3 ms | 4480 KB |
10_16.txt | AC | 18 ms | 4480 KB |
10_17.txt | AC | 18 ms | 4480 KB |
20_01.txt | AC | 1071 ms | 8960 KB |
20_02.txt | AC | 1117 ms | 8960 KB |
20_03.txt | AC | 1126 ms | 8832 KB |
20_04.txt | AC | 68 ms | 5120 KB |
20_05.txt | AC | 7 ms | 4352 KB |
20_06.txt | AC | 4 ms | 4992 KB |
20_07.txt | AC | 5 ms | 4480 KB |
20_08.txt | AC | 1250 ms | 5248 KB |
20_09.txt | AC | 4 ms | 4480 KB |
20_10.txt | AC | 79 ms | 5120 KB |
20_11.txt | AC | 1879 ms | 5376 KB |
20_12.txt | AC | 26 ms | 7936 KB |
20_13.txt | AC | 65 ms | 8704 KB |
20_14.txt | AC | 77 ms | 8832 KB |
20_15.txt | TLE | 2107 ms | 11256 KB |
20_16.txt | TLE | 2104 ms | 9208 KB |