AGC012 B. Splatter Painting

問題

連結とは限らない、N頂点、M本の辺を持つ無向グラフが与えられる。
頂点には1～Nの番号が振られている。
Q回「頂点v_jから距離d_jの頂点を色c_jで塗る」という操作をした後の各頂点の色が何色か答えよ。

制約

1 <= N,M,Q <= 10^5
0 <= d <= 10
1 <= c_j <= 10^5
自己ループや多重辺は存在しない

解説

https://atcoder.jp/img/agc012/editorial.pdf
AtCoder Grand Contest 012 解説放送 - YouTube

愚直な方法を考える。
操作をそのまま実行して、頂点vから深さdまで実際にたどって色cで塗ることを繰り返す。
ただ、この方法だと色を塗る頂点が全頂点になる可能性があり、O(Q*N)だと間に合わない。

そこで、無駄なことをしているところを考える。

一つは、1度塗った頂点を別な色に塗り替えている部分が考えられる。
これは、与えられたクエリを逆順に実行すれば、すでに色が塗られているところは塗り返さなくてよくなる。
ただ、この方法でも、すでに塗った頂点を超えて塗らないといけないため計算量は変わらない。
(例：[1]-[2]-[3]というグラフで(「v=1,d=2,c=2」→「v=2,d=0,c=1」だと、逆順に頂点2から塗っても頂点1から塗るとき、すでに塗った頂点2を超えて頂点3を塗らないといけない)

さらに、無駄な移動がないかよく考えると、「ある頂点vに深さdで色cで塗りに来た」場合、すでに「頂点vに深さd'(>=d)で色c'で塗りに来ていた」場合は塗ることはないことがわかる。
なので、それを以下のようにメモって無駄な移動をしないようにする。
dp[v][d]:=頂点vに深さdですでに色を塗ったか
(coloring(v,d,c)で頂点vで来たら隣接ノードuにcoloring(u,d-1,c)で塗りに行けばよい)

反省

制約の中で異様なd<=10をうまく活用することを考えたほうがよい。
色を塗るとき、visited[v]をメモリながらbfsしていたけど、上みたいなメモ化しながらdfs(v,d)でdを減らしながら辿るのも考える。