Submission #1886810
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include<complex>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;
const int MAX = 1000 * 100 + 47;
struct Item
{
int v, d, c;
};
Item Q[MAX];
vector<int> g[MAX];
int U[MAX];
int D[MAX];
int C[MAX];
int iter;
void dfs(int v, int d, int curD, int color)
{
if (d > curD) return;
if (curD - d <= D[v]) return;
D[v] = curD - d;
if (C[v] == 0) C[v] = color;
FOR(i, 0, SZ(g[v]))
{
int to = g[v][i];
dfs(to, d + 1, curD, color);
}
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//ios::sync_with_stdio(false); cin.tie(0);
int n, m;
cin >> n >> m;
FOR(i, 0, m)
{
int a, b;
cin >> a >> b;
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
}
int q;
cin >> q;
FOR(i, 0, q)
{
cin >> Q[i].v >> Q[i].d >> Q[i].c;
Q[i].v--;
}
reverse(Q, Q + q);
FILL(D, -1);
FOR(i, 0, q)
{
dfs(Q[i].v, 0, Q[i].d, Q[i].c);
}
FOR(i, 0, n)
{
//cout << i + 1 << ": " << C[i] << "\n";
cout << C[i] << "\n";
}
}
Submission Info
Submission Time |
|
Task |
B - Splatter Painting |
User |
vjudge1 |
Language |
C++14 (Clang 3.8.0) |
Score |
700 |
Code Size |
1834 Byte |
Status |
AC |
Exec Time |
416 ms |
Memory |
8824 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 |
2 ms |
3328 KB |
00_example_02.txt |
AC |
2 ms |
3328 KB |
10_01.txt |
AC |
4 ms |
3456 KB |
10_02.txt |
AC |
2 ms |
3328 KB |
10_03.txt |
AC |
2 ms |
3328 KB |
10_04.txt |
AC |
2 ms |
3328 KB |
10_05.txt |
AC |
4 ms |
3456 KB |
10_06.txt |
AC |
2 ms |
3328 KB |
10_07.txt |
AC |
3 ms |
3456 KB |
10_08.txt |
AC |
9 ms |
3456 KB |
10_09.txt |
AC |
9 ms |
3456 KB |
10_10.txt |
AC |
9 ms |
3456 KB |
10_11.txt |
AC |
9 ms |
3456 KB |
10_12.txt |
AC |
9 ms |
3456 KB |
10_13.txt |
AC |
6 ms |
3456 KB |
10_14.txt |
AC |
6 ms |
3456 KB |
10_15.txt |
AC |
5 ms |
3456 KB |
10_16.txt |
AC |
9 ms |
3456 KB |
10_17.txt |
AC |
9 ms |
3456 KB |
20_01.txt |
AC |
405 ms |
8192 KB |
20_02.txt |
AC |
406 ms |
8064 KB |
20_03.txt |
AC |
416 ms |
8064 KB |
20_04.txt |
AC |
67 ms |
4096 KB |
20_05.txt |
AC |
13 ms |
3456 KB |
20_06.txt |
AC |
34 ms |
4096 KB |
20_07.txt |
AC |
14 ms |
3456 KB |
20_08.txt |
AC |
132 ms |
4352 KB |
20_09.txt |
AC |
13 ms |
3456 KB |
20_10.txt |
AC |
133 ms |
4352 KB |
20_11.txt |
AC |
174 ms |
4608 KB |
20_12.txt |
AC |
200 ms |
7040 KB |
20_13.txt |
AC |
334 ms |
7936 KB |
20_14.txt |
AC |
368 ms |
8064 KB |
20_15.txt |
AC |
386 ms |
8696 KB |
20_16.txt |
AC |
386 ms |
8824 KB |