题目

Vjudge https://vjudge.net/problem/AtCoder-2362 原网址 http://agc012.contest.atcoder.jp/tasks/agc012_b

Problem Statement

Squid loves painting vertices in graphs.

There is a simple undirected graph consisting of N vertices numbered 1 through N, and M edges. Initially, all the vertices are painted in color 0. The i-th edge bidirectionally connects two vertices ai and bi. The length of every edge is 1.

Squid performed Q operations on this graph. In the i-th operation, he repaints all the vertices within a distance of di from vertex vi, in color ci.

Find the color of each vertex after the Q operations.

Constraints

1≤N,M,Q≤105 1≤ai,bi,vi≤N ai≠bi 0≤di≤10 1≤ci≤10^5 di and ci are all integers. There are no self-loops or multiple edges in the given graph.

Input

Input is given from Standard Input in the following format:

N M a1 b1 : aM bM Q v1 d1 c1 : vQ dQ cQ

The given graph may not be connected.

Output

Print the answer in N lines. In the i-th line, print the color of vertex i after the Q operations.

Samples

No.InputOutput17 71 21 31 44 55 65 72 326 1 11 2 22222210214 101 45 77 114 1014 714 36 148 115 138 388 6 29 7 856 9 36 7 510 3 112 9 49 6 68 2 310315533613453

分析

题意就是给个n个点的图，m个操作，每次选择一个点v[i]把与它距离不大于d[i]的点染成颜色c[i]，问最后每个点的颜色。看看数据范围（除了d[] 只有10，每个数都达到100000），直接暴力修改肯定不行。可以发现，暴力之所以这么慢，是因为有许多重复染色的多余操作，那么我们把它离线化处理，从后往前，这样染过色的点就不用染（可是却还需要继续往下递归，因为不能保证下面的都是这个颜色）还有一点，假如点 x 要把离它 dx 的点染色，而在这之前与它相邻的点 y已经把离它 dy 的点染过色了，这时要是 dy>=dx ，那么 x 的这一操作完全可以省去了，这样就的确快了许多。可以证明一下，每个点最多被讨论 10 次（因为 d[] 最多为10），所以时间复杂度为 10n。

代码

#include <cstdio> #define For(x) for (int h=head[x],o=V[h]; h; o=V[h=to[h]]) #define add(u,v) (to[++num]=head[u],head[u]=num,V[num]=v) int num,head[100005],to[200005],V[200005]; int Q,n,m,v[100005],d[100005],c[100005],cl[100005],rg[100005]; void dfs(int x,int ran,int col){ if (rg[x]>=ran || ran<=0) return; rg[x]=ran; //范围 if (!cl[x]) cl[x]=col; //颜色 For(x) dfs(o,ran-1,col); } int main(){ freopen("1.txt","r",stdin); scanf("%d%d",&n,&m); for (int i=1,x,y; i<=m; i++){ scanf("%d%d",&x,&y); add(x,y); add(y,x); } scanf("%d",&Q); for (int i=1; i<=Q; i++) scanf("%d%d%d",&v[i],&d[i],&c[i]); for (int i=Q; i; i--) dfs(v[i],d[i]+1,c[i]); for (int i=1; i<=n; i++) printf("%d\n",cl[i]); }