Submission #1197605
Source Code Expand
#include<stdio.h>
#include<vector>
#include<queue>
//#define getchar_unlocked getchar
//#define putchar_unlocked putchar
#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];
bool used[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]--;
}
memset(mq, -1, sizeof(mq));
for (int i = q - 1; i >= 0; i--) {
int s = 0, g = 0;
if (c2[v[i]] == -1) { c1[v[i]] = c[i]; mq[v[i]] = d[i]; c2[v[i]] = i; }
d1[v[i]] = 0; used[v[i]] = 1;
if (d1[v[i]] < d[i])que[g++] = v[i];
memset(used, 0, sizeof(used));
while (s != g) {
int p = que[s++];
int siz = E[p].size();
rep(j, siz) {
int u = E[p][j];
if (mq[u] >= d[i] - d1[u])continue;
if (c2[u] == -1) {
c1[u] = c[i]; c2[u] = i; d1[u] = d1[p] + 1;
mq[u] = d[i] - d1[u];
}
if (!used[u] && d1[u] < d[i]) {
used[u] = 1; 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 |
0 |
Code Size |
2067 Byte |
Status |
WA |
Exec Time |
2104 ms |
Memory |
9336 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
3 ms |
4864 KB |
00_example_02.txt |
AC |
3 ms |
4864 KB |
10_01.txt |
AC |
3 ms |
4864 KB |
10_02.txt |
AC |
3 ms |
4864 KB |
10_03.txt |
AC |
3 ms |
4864 KB |
10_04.txt |
AC |
3 ms |
4864 KB |
10_05.txt |
AC |
3 ms |
4864 KB |
10_06.txt |
AC |
3 ms |
4864 KB |
10_07.txt |
AC |
3 ms |
4864 KB |
10_08.txt |
WA |
17 ms |
4864 KB |
10_09.txt |
WA |
13 ms |
4864 KB |
10_10.txt |
WA |
17 ms |
4864 KB |
10_11.txt |
WA |
13 ms |
4864 KB |
10_12.txt |
WA |
12 ms |
4864 KB |
10_13.txt |
WA |
4 ms |
4864 KB |
10_14.txt |
WA |
4 ms |
4864 KB |
10_15.txt |
WA |
3 ms |
4864 KB |
10_16.txt |
AC |
17 ms |
4992 KB |
10_17.txt |
AC |
27 ms |
4992 KB |
20_01.txt |
TLE |
2104 ms |
8576 KB |
20_02.txt |
TLE |
2104 ms |
8576 KB |
20_03.txt |
TLE |
2104 ms |
8576 KB |
20_04.txt |
AC |
51 ms |
5504 KB |
20_05.txt |
WA |
38 ms |
4864 KB |
20_06.txt |
AC |
19 ms |
5120 KB |
20_07.txt |
WA |
29 ms |
4864 KB |
20_08.txt |
AC |
1581 ms |
5632 KB |
20_09.txt |
WA |
21 ms |
4864 KB |
20_10.txt |
WA |
444 ms |
5504 KB |
20_11.txt |
TLE |
2104 ms |
5888 KB |
20_12.txt |
WA |
63 ms |
8064 KB |
20_13.txt |
WA |
566 ms |
8832 KB |
20_14.txt |
WA |
981 ms |
8960 KB |
20_15.txt |
TLE |
2104 ms |
9336 KB |
20_16.txt |
TLE |
2104 ms |
9336 KB |