http://agc012.contest.atcoder.jp/submissions/1414860
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.
自行翻译 大致是有n个点m条边 q个操作 每个操作是将点u及到它距离在d以内的点染上c
我们可以从后向前找 这样就不会重复染色 另外我们可以对每个点向外的范围进行记录，扫描时如果剩下的范围小于点上标记的范围 就不要扫下去了 （manacher？？）
var i,j,k,l,m,n,q,w,x,y,t:longint; st,ed,first,next,d,v,color,fw,c:array[1..200000] of longint; b:array[1..200000]of boolean; procedure ad(p,o:longint); begin t:=t+1; ed[t]:=o; next[t]:=first[p];first[p]:=t; end; procedure dfs(p,o,cl:longint); var i,j:longint; begin if fw[p]>=o then exit; i:=first[p]; fw[p]:=o; b[p]:=true; if color[p]=0 then color[p]:=cl; while (i>=1) do begin if b[ed[i]]=false then dfs(ed[i],o-1,cl); i:=next[i]; end; b[p]:=false; end; begin readln(n,m); for i:=1 to m do first[i]:=-1; fillchar(fw,sizeof(fw),255); for i:=1 to m do begin readln(x,y); ad(x,y);ad(y,x); end; readln(q); for i:=1 to q do readln(v[i],d[i],c[i]); for i:=q downto 1 do begin dfs(v[i],d[i],c[i]); end; for i:=1 to n do writeln(color[i]); end.、
