Submission #1679684

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>

template <typename Tp>Tp Max(const Tp &a, const Tp &b) {return a > b ? a : b;}
template <typename Tp>Tp Min(const Tp &a, const Tp &b) {return a < b ? a : b;}

template <typename Tp>void Read(Tp &x) {
	Tp in = 0, f = 1; char ch = getchar();
	while(ch<'0' || ch>'9') {if(ch=='-') f = -1; ch = getchar();}
	while(ch>='0' && ch<='9') {in = in*10+ch-'0'; ch = getchar();}
	x = in*f;
}

const int SN = 1000000 + 10;

int max[SN], v[SN], c[SN], deep[SN], head[SN], finl[SN], n, m, q;

int num;

struct Edge {
	int v, next;
}E[SN];

void Add(int u, int v) {
	E[++num].v = v, E[num].next = head[u], head[u] = num;
}

void Dfs(int now, int fa, int d, int c) {
	if(max[now] >= d) return ;

	max[now] = d;

	if(!finl[now]) finl[now] = c;
	
	if(!d) return ;
	
	for(int i = head[now]; i; i = E[i].next) {
		int to = E[i].v;
		if(to != fa) Dfs(to, now, d-1, c);
	}
}

int main() {
	int x = 0, y = 0, z = 0;

	memset(max, -1, sizeof max);
	
	Read(n), Read(m);

	for(int i = 1; i <= m; i++) Read(x), Read(y), Add(x, y), Add(y, x);

	Read(q);
	
	for(int i = 1; i <= q; i++) Read(v[i]), Read(deep[i]), Read(c[i]);

	for(int i = q; i >= 1; i--) Dfs(v[i], 0, deep[i], c[i]);

	for(int i = 1; i <= n; i++) printf("%d\n", finl[i]);

	return 0;
}

Submission Info

Judge Result