Submission #2835954
Source Code Expand
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define INF 1LL<<50
#define fst first
#define sec second
#define pb push_back
#define int long long
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(int itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(int itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define debug(x) cout << #x << " = " << (x) << endl;
typedef long long ll;
typedef pair<ll,ll> P;
int color[100001] = {};
int dist[100001] = {};
vector <int>edge[100001];
void dfs(int v, int d, int c){
if(color[v] == 0) color[v] = c; //未訪問なら色づけ
if(dist[v] >= d) return; // すでにその点からd以下の点は訪問済み
dist[v] = d;
REP(i,edge[v].size()){
dfs(edge[v][i],d-1,c);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin >> n >> m;
REP(i,m){
int a,b;
cin >> a >> b;
a--;b--;
edge[a].push_back(b);
edge[b].push_back(a);
}
int q;
cin >> q;
vector<tuple<int,int,int>> tp;
REP(_,q){
int v,d,c;
cin >> v >> d >> c;
tp.pb(make_tuple(v-1,d,c));
}
RREP(i,q){
int v,d,c;
tie(v,d,c) = tp[i];
dfs(v,d,c);
}
REP(i,n) cout << color[i] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Splatter Painting |
User |
cinnamoroll |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
1487 Byte |
Status |
AC |
Exec Time |
228 ms |
Memory |
12400 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 |
2560 KB |
00_example_02.txt |
AC |
2 ms |
2560 KB |
10_01.txt |
AC |
3 ms |
2688 KB |
10_02.txt |
AC |
2 ms |
2560 KB |
10_03.txt |
AC |
2 ms |
2560 KB |
10_04.txt |
AC |
2 ms |
2560 KB |
10_05.txt |
AC |
3 ms |
2688 KB |
10_06.txt |
AC |
2 ms |
2560 KB |
10_07.txt |
AC |
5 ms |
2688 KB |
10_08.txt |
AC |
6 ms |
2816 KB |
10_09.txt |
AC |
6 ms |
2816 KB |
10_10.txt |
AC |
6 ms |
2816 KB |
10_11.txt |
AC |
6 ms |
2816 KB |
10_12.txt |
AC |
6 ms |
2816 KB |
10_13.txt |
AC |
6 ms |
2688 KB |
10_14.txt |
AC |
6 ms |
2688 KB |
10_15.txt |
AC |
5 ms |
2688 KB |
10_16.txt |
AC |
6 ms |
2816 KB |
10_17.txt |
AC |
6 ms |
2816 KB |
20_01.txt |
AC |
227 ms |
10608 KB |
20_02.txt |
AC |
228 ms |
10864 KB |
20_03.txt |
AC |
228 ms |
12400 KB |
20_04.txt |
AC |
25 ms |
3840 KB |
20_05.txt |
AC |
4 ms |
2944 KB |
20_06.txt |
AC |
149 ms |
4544 KB |
20_07.txt |
AC |
5 ms |
2944 KB |
20_08.txt |
AC |
20 ms |
7284 KB |
20_09.txt |
AC |
5 ms |
2944 KB |
20_10.txt |
AC |
19 ms |
5876 KB |
20_11.txt |
AC |
25 ms |
7028 KB |
20_12.txt |
AC |
172 ms |
8060 KB |
20_13.txt |
AC |
202 ms |
10992 KB |
20_14.txt |
AC |
200 ms |
10096 KB |
20_15.txt |
AC |
200 ms |
11372 KB |
20_16.txt |
AC |
202 ms |
11628 KB |