Submission #3248840
Source Code Expand
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;
template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);
struct edge{int to, cost;};
class Graph
{
public:
int V;
vector<vector<edge>> G;
Graph(int V): V(V){
G = vector<vector<edge>>(V, vector<edge>(0));
}
void add_edge(int from, int to, int cost){
G[from].push_back(edge({to, cost}));
}
void add_edge2(int v1, int v2, int cost){
add_edge(v1, v2, cost);
add_edge(v2, v1, cost);
}
void dfs(int v, int d, int i, vector<Pii> &ans){
if(ans[v].first == i || d <= ans[v].second) return;
if(ans[v].first == -1) ans[v] = Pii(i, d);
if(d > ans[v].second) ans[v].second = d;
if(d > 0){
REP(k, G[v].size()) dfs(G[v][k].to, d - 1, i, ans);
}
}
};
signed main(){
int N, M; cin >> N >> M;
Graph G(N);
int a, b;
REP(i, M){
cin >> a >> b;
G.add_edge2(a - 1, b - 1, 1);
}
int Q; cin >> Q;
vec v(Q), d(Q), c(Q);
REP(i, Q){
cin >> v[i] >> d[i] >> c[i];
v[i]--;
}
vector<Pii> ans(N, Pii(-1, -1));
IREP(i, Q) G.dfs(v[i], d[i], i, ans);
REP(i, N){
if(ans[i].first == -1) cout << 0 << endl;
else cout << c[ans[i].first] << endl;
}
return 0;
}
template<typename T>
void readvec(vector<T> &a){
REP(i, a.size()){
cin >> a[i];
}
}
void readindex(vector<int> &a){
REP(i, a.size()){
cin >> a[i];
a[i]--;
}
}
Submission Info
Submission Time |
|
Task |
B - Splatter Painting |
User |
sumitacchan |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2190 Byte |
Status |
WA |
Exec Time |
318 ms |
Memory |
12160 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 |
1 ms |
256 KB |
00_example_02.txt |
AC |
1 ms |
256 KB |
10_01.txt |
WA |
2 ms |
384 KB |
10_02.txt |
AC |
1 ms |
256 KB |
10_03.txt |
AC |
1 ms |
256 KB |
10_04.txt |
AC |
1 ms |
256 KB |
10_05.txt |
WA |
2 ms |
384 KB |
10_06.txt |
AC |
1 ms |
256 KB |
10_07.txt |
AC |
4 ms |
256 KB |
10_08.txt |
WA |
7 ms |
512 KB |
10_09.txt |
WA |
7 ms |
512 KB |
10_10.txt |
WA |
7 ms |
512 KB |
10_11.txt |
WA |
7 ms |
512 KB |
10_12.txt |
WA |
7 ms |
512 KB |
10_13.txt |
AC |
5 ms |
384 KB |
10_14.txt |
AC |
5 ms |
384 KB |
10_15.txt |
AC |
5 ms |
384 KB |
10_16.txt |
AC |
6 ms |
512 KB |
10_17.txt |
AC |
6 ms |
512 KB |
20_01.txt |
WA |
315 ms |
12160 KB |
20_02.txt |
WA |
318 ms |
12160 KB |
20_03.txt |
WA |
318 ms |
12160 KB |
20_04.txt |
WA |
39 ms |
2560 KB |
20_05.txt |
WA |
6 ms |
384 KB |
20_06.txt |
AC |
151 ms |
4352 KB |
20_07.txt |
WA |
6 ms |
512 KB |
20_08.txt |
WA |
47 ms |
2304 KB |
20_09.txt |
WA |
6 ms |
384 KB |
20_10.txt |
WA |
46 ms |
2048 KB |
20_11.txt |
WA |
61 ms |
2816 KB |
20_12.txt |
AC |
214 ms |
8960 KB |
20_13.txt |
AC |
275 ms |
10880 KB |
20_14.txt |
AC |
289 ms |
11008 KB |
20_15.txt |
AC |
287 ms |
11376 KB |
20_16.txt |
AC |
288 ms |
11632 KB |