No.010 D

ある仲間に情報を伝えたとき, その仲間からどの仲間に情報を伝えられるかで有向グラフを作り, 連結なグラフごとに強連結成分分解して入力辺がない頂点数を数えるというのが基本方針である. このうち, 有向グラフ作成は愚直にやると $O(N(N+M))$ かかるので, ここをなんとかしなければならない.

ある仲間から別の仲間への距離が一番近いスパイより近ければ情報を伝えられる.

一番近いスパイをどう求めるかであるが, $M \leq 5000$ のときはすべてのスパイとの距離を計算すればいい.

$M \gt 5000$ のときは, スパイがランダムに配置されることを利用する. 平面を $100 \times 100$ のマスに区切ってどのマスにスパイが配置されているかを記録しておく. ひとつのマスの大きさは縦横 $S = 2 \times 10^7$ である. 注目している仲間のいるマスの周囲8近傍のマス内に一番近いスパイがいる可能性は十分に高く, この周囲8近傍内のマスにいるスパイだけを調べればいい.