グラフを考える。ある頂点から距離d(0≦d≦10)以内を色cで塗る、というクエリをQ(0≦Q≦10^5)個処理するとき、最終的な各頂点の色を求めよ
一番最後のクエリのみが反映される→クエリを逆順に考える
dが小さいのでナイーブにやってもC++ならできそう。ただしJavaだと無理(Javaの場合O(1000万)はTLEすると思うべし。
点vから距離d1以内の点をダイクストラ or BFSで再帰的(？)に塗っていく。ただし、点vから距離l離れた点uについて、同じように距離d2以内の点を塗るというクエリについては、d2<d1 - l のときは塗らない、という枝刈りができる。
agc012.contest.atcoder.jp
