AtCoder / 民族大移動 - ふくほのひとりごと。

ふくほです。
ABC024-C 民族大移動
を解きました。
atcoder.jp

愚直に解くと $O(KN)$ 。
今回の制約では $KN$ は高々 $10^6$
程度なので、間に合いそうです。

出発地と比べて目的地の
数字が大きい場合は
目的地にたどり着くまで
大きな数字の街に移動させます。
その逆もやります。

目的地にたどり着いた時点で、
その民族に対する計算を辞めます。

今回は愚直解で間に合ったけど、
もしも間に合わなかったら
どうやって計算量減らすんだろ…

最近コンテストに出てる感想だと
やたらと制約がきついので
今後はこれの $NK\geq 10^9$ とか
出てきそうで怖いなぁと思います。