Submission #1368996

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define skip continue
#define pb push_back

const int N = 1e5 + 10;

int n, m, q, x[N], dist[N], col[N], color[N];
vector <int> v[N];
bool u[N];

void dfs(int pos, int len, int d, int c){
	u[pos] = 1;
	color[pos] = c;
	if(len == d) return;
	for(int i = 0; i < v[pos].size(); ++ i){
		int to = v[pos][i];
		if(!u[to]){
			dfs(to, len + 1, d, c);
		}
	}
}

void change(int pos, int d, int c){
	dfs(pos, 0, d, c);
}

int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; ++ i){
		int x1, y;
		cin >> x1 >> y;
		v[x1].pb(y);
		v[y].pb(x1);
	}
	//cerr << "OK " << n << ' ' << m << '\n';
	cin >> q;
	for(int i = 1; i <= q; ++ i){
		cin >> x[i] >> dist[i] >> col[i];
	}
	
	for(int i = q; i >= 1; -- i){
		if(u[x[i]]) skip;
		change(x[i], dist[i], col[i]);
	}
	//cerr << n << ' ' << m << '\n';
	for(int i = 1; i <= n; ++ i){
		cout << color[i] << '\n';
	}
	return 0;
}

Submission Info

Judge Result