読者です 読者をやめる 読者になる 読者になる

アルゴリズム忘備録

競技プログラミングとかデータ分析とか

AtCoder Grand Contest 012 B - Splatter Painting

 

グラフを考える。ある頂点から距離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