競技プログラミング

ABC087-D「People on a Line」を解きました

D – People on a Line

配点 : 400

問題文

x 軸上に N 人の人が立っています。
i の位置を x_i とします。
任意の i に対して、x_i0 以上 10^9 以下の整数です。
同じ位置に複数の人が立っていることもありえます。

これらの人の位置に関する情報が M 個与えられます。
このうち i 個めの情報は (L_i, R_i, D_i) という形をしています。
この情報は、人 R_i は人 L_i よりも距離 D_i だけ右にいること、
すなわち、x_{R_i} – x_{L_i} = D_i が成り立つことを表します。

これら M 個の情報のうちのいくつかに誤りがある可能性があることがわかりました。
与えられる M 個すべての情報と矛盾しないような値の組 (x_1, x_2, …, x_N) が存在するかどうか判定してください。

制約

  • 1 <= N <= 100,000
  • 0 <= M <= 200,000
  • 1 <= L_i, R_i <= N (1 <= i <= M)
  • 0 <= D_i <= 10,000 (1 <= i <= M)
  • L_i ≠ R_i (1 <= i <=M)
  • i ≠ j のとき、(L_i, R_i) \≠ (L_j, R_j) かつ (L_i, R_i) ≠ (R_j, L_j)
  • D_i は整数である

考えたこと

グラフを作ってなんとかしようと思いました。どこを始点にしてもいいようにL->Rの重みdの有向辺だけでなくR->Lの重み-dの辺も追加しておくとよさそうです。

どこかの点を始点に距離0としてから幅優先探索なんかで枝を伝ってどんどん距離を決めていけば良さそうです。どこかで矛盾が生じた時点でNoを出力すればよく、最後まで矛盾なくいければYesになります。

ただ注意しなければいけないのはグラフが連結しているとは限らないことです。なのでforループを回して全ての点について未探索であればそこを0として探索をしなければなりません。

ソースコード