ABC203 C Friends and Travel costs
まず, あらかじめ友達を
$ A_i
の昇順にソートしておく. すると友達を前から順に見ていくと, 前の友達がどこにいるかという情報を持っておくことで, 太郎君の最終的にたどり着く村の番号は高速に求められる. 計算量はソートがボトルネックとなり
$ O(N \log N)
となる.
実装例:
https://atcoder.jp/contests/abc203/submissions/23042003