Consistent Ave

解説

証言をもとにグラフを作成することができます。

各連結成分ことに、１人を０点とすることによりその連結成分内の人の点数が一意に定まります。

DFS/BFSを行います。

各頂点から別の頂点へ移動する時、まだ訪れていない頂点であれば点を定め、すでに訪れている頂点であれば点差が正しいかを判定します。そして、その連結成分内での最大値と最小値が$10^9$以下であるかを確認すればよいです。

また、重みつきUFでも解くことができます。実装例

実装

Rust

C++