AT_arc090_b [ABC087D] People on a Line

[problemUrl]: https://atcoder.jp/contests/abc087/tasks/arc090_b $ x $ 軸上に $ N $ 人の人が立っています。 人 $ i $ の位置を $ x_i $ とします。 任意の $ i $ に対して、$ x_i $ は $ 0 $ 以上 $ 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) $ が存在するかどうか判定してください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 100,000 $ - $ 0\ \leq\ M\ \leq\ 200,000 $ - $ 1\ \leq\ L_i,\ R_i\ \leq\ N $ ($ 1\ \leq\ i\ \leq\ M $) - $ 0\ \leq\ D_i\ \leq\ 10,000 $ ($ 1\ \leq\ i\ \leq\ M $) - $ L_i\ \neq\ R_i $ ($ 1\ \leq\ i\ \leq\ M $) - $ i\ \neq\ j $ のとき、$ (L_i,\ R_i)\ \neq\ (L_j,\ R_j) $ かつ $ (L_i,\ R_i)\ \neq\ (R_j,\ L_j) $ - $ D_i $ は整数である ### Sample Explanation 1 値の組 $ (x_1,\ x_2,\ x_3) $ として、$ (0,\ 1,\ 2) $ や $ (101,\ 102,\ 103) $ などが考えられます。 ### Sample Explanation 2 はじめの $ 2 $ つの情報が正しいとすると、$ x_3\ -\ x_1\ =\ 2 $ が成り立つことが分かります。 これは最後の情報に矛盾します。