graphライブラリ貼るだけだったのに、貼るライブラリを間違えてWAをたくさん生やした。find木で解こうとしていた。10^5$)の敵がいる。敵に知られずに、あなたが持っているある情報を仲間全員で共有したい。ある仲間が情報を得ると、その仲間はスピーカーを用いて適当な半径$r$以内の全ての人間に情報を伝えることができる。このことから、あなたが直接情報を伝えれば、連鎖的に情報を伝達させることができる。情報を伝えなければいけないの最低で何人か。解法それぞれの仲間は敵に聞こえない最大の大きさで情報を拡散すればよい。この情報の伝達関係の有向グラフを作る。その推移閉包を考え、これの点被覆の大きさを答えればよい。具体的に言うと、まず1回のスピーカーによる拡散に関する伝達関係の有向グラフを作る。これは$O(nm)$で構成すれば間に合う。整数で取り扱えばよい。次に情報を直接伝えるべき仲間を表す頂点を探す。そのような頂点の集合は、その要素の頂点から到達できる頂点を全て集めると、頂点全体になっている。推移閉包の点被覆である。入次数が$0$の頂点は、明らかに点被覆に入る。考えたとき閉路が問題となるが、これは事前に強連結成分分解をすれば回避できる。有向非巡回グラフ(DAG)になっていれば、入次数が$0$でない点は何らかの入次数が$0$の点から到達できるので、これだけを行えば答えが得られる。この部分は$O(N^2)$である。以前書いた強連結成分分解を投げたらMLEしたので、ちゃんと開放が走るように修正をした。