Problem:


Score : 400 points

Problem Statement

There are N people standing on the x-axis.
Let the coordinate of Person i be x_i.
For every i, x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people.
The i-th piece of information has the form (L_i, R_i, D_i).
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.

It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.

Constraints

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)

If i \neq j, then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j).

D_i are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 D_1
L_2 R_2 D_2
:
L_M R_M D_M

Output

If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103).

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
重み付きunionfindを使う
https://qiita.com/drken/items/cce6fc5c579051e64fab
http://at274.hatenablog.com/entry/2018/02/03/140504


5 4
1 2 2
2 3 3
4 5 4
2 5 10
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def calc_weight(self, x):
        self.find(x) #圧縮
        return self.weight[x]

    def calc_diff(self, x, y):
        return self.calc_weight(y) - self.calc_weight(x)

    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] = - w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0


    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        # print(d,uf.calc_diff(l,r))
        if d == uf.calc_diff(l, r):
            continue
        else:
            print("No")
            exit()
print("Yes")
# for i in uf.parent.keys():
    # uf.find(i)
#     print("index:{} rank:{}, parent:{}, weight:{}".format(i,uf.rank[i],uf.parent[i],uf.weight[i]))

Submission status: Wrong Answer

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
重み付きunionfindを使う
https://qiita.com/drken/items/cce6fc5c579051e64fab
http://at274.hatenablog.com/entry/2018/02/03/140504


5 4
1 2 2
2 3 3
4 5 4
2 5 10
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def calc_weight(self, x):
        self.find(x) #圧縮
        return self.weight[x]

    def calc_diff(self, x, y):
        return self.calc_weight(y) - self.calc_weight(x)

    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] = w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0


    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        # print(d,uf.calc_diff(l,r))
        if d == uf.calc_diff(l, r):
            continue
        else:
            print("No")
            exit()
print("Yes")
# for i in uf.parent.keys():
    # uf.find(i)
#     print("index:{} rank:{}, parent:{}, weight:{}".format(i,uf.rank[i],uf.parent[i],uf.weight[i]))

Submission status: Wrong Answer

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
重み付きunionfindを使う
https://qiita.com/drken/items/cce6fc5c579051e64fab
http://at274.hatenablog.com/entry/2018/02/03/140504


5 4
1 2 2
2 3 3
4 5 4
2 5 10
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def calc_weight(self, x):
        self.find(x) #圧縮
        return self.weight[x]

    def calc_diff(self, x, y):
        return self.calc_weight(y) - self.calc_weight(x)

    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] = w + self.weight[x] - self.weight[w]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0


    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        # print(d,uf.calc_diff(l,r))
        if d == uf.calc_diff(l, r):
            continue
        else:
            print("No")
            exit()
print("Yes")
# for i in uf.parent.keys():
#     uf.find(i)
#     print("index:{} rank:{}, parent:{}, weight:{}".format(i,uf.rank[i],uf.parent[i],uf.weight[i]))

Submission status: Wrong Answer

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
重み付きunionfindを使う
https://qiita.com/drken/items/cce6fc5c579051e64fab
http://at274.hatenablog.com/entry/2018/02/03/140504


5 4
1 2 2
2 3 3
4 5 4
2 5 10
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def calc_weight(self, x):
        self.find(x) #圧縮
        return self.weight[x]

    def calc_diff(self, x, y):
        return self.calc_weight(y) - self.calc_weight(x)

    def weighted_union(self, x, y, w):
        wx = self.calc_weight(x)
        wy = self.calc_weight(y)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = w - wx - wy
        else:
            self.parent[py] = px
            self.weight[py] = w - wx - wy
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0


    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        if d == uf.calc_diff(l, r):
            continue
        else:
            print("No")
            exit()
print("Yes")
# for i in uf.parent.keys():
#     uf.find(i)
#     print("index:{} rank:{}, parent:{}, weight:{}".format(i,uf.rank[i],uf.parent[i],uf.weight[i]))

Submission status: Wrong Answer

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
重み付きunionfindを使う
https://qiita.com/drken/items/cce6fc5c579051e64fab
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)  
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = self.find(self.parent[x])     #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def calc_weight(self, x):
        self.find(x) #圧縮
        return self.weight[x]

    def calc_diff(self, x, y):
        return self.calc_weight(y) - self.calc_weight(x)

    def weighted_union(self, x, y, w):
        wx = self.calc_weight(x)
        wy = self.calc_weight(y)
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if x == y: return 0
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.weight[x] = w - wx - wy
        else:
            self.parent[y] = x
            self.weight[y] = w - wx - wy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        return 0


    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        if d == uf.calc_diff(l, r):
            continue
        else:
            print("No")
            exit()
print("Yes")
# for i in uf.parent.keys():
#     uf.find(i)
#     print("index:{} rank:{}, parent:{}, weight:{}".format(i,uf.rank[i],uf.parent[i],uf.weight[i]))

Submission status: Wrong Answer

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
重み付きunionfindを使う
https://qiita.com/drken/items/cce6fc5c579051e64fab
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)           
            self.parent[x] = self.find(self.parent[x])      #親の置き換え(圧縮)
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def calc_weight(self, x):
        self.find(x) #圧縮
        return self.weight[x]

    def calc_diff(self, x, y):
        return self.calc_weight(y) - self.calc_weight(x)

    def weighted_union(self, x, y, w):
        wx = self.calc_weight(x)
        wy = self.calc_weight(y)
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if x == y: return 0
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.weight[x] = w - wx + wy
        else:
            self.parent[y] = x
            self.weight[y] = w + wx - wy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        return 0


    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        if d == uf.calc_diff(l, r):
            continue
        else:
            print("No")
            exit()
print("Yes")
# for i in uf.parent.keys():
#     print("index:{} rank:{}, parent:{}, weight:{}".format(i,uf.rank[i],uf.parent[i],uf.weight[i]))

Submission status: Wrong Answer

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
重み付きunionfindを使う
https://qiita.com/drken/items/cce6fc5c579051e64fab
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)           
            self.parent[x] = self.find(self.parent[x])      #親の置き換え(圧縮)
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def calc_weight(self, x):
        self.find(x) #圧縮
        return self.weight[x]


    def weighted_union(self, x, y, w):
        wx = self.calc_weight(x)
        wy = self.calc_weight(y)
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if x == y: return 0
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.weight[x] = w - wx + wy
        else:
            self.parent[y] = x
            self.weight[y] = w + wx - wy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        return 0


    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
infos = []
for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        uf.find(r)
        uf.find(l)
        if d == (uf.weight[r]-uf.weight[l]):
            continue
        else:
            print("No")
            exit()
print("Yes")
# for i in uf.parent.keys():
#     print("index:{} rank:{}, parent:{}, weight:{}".format(i,uf.rank[i],uf.parent[i],uf.weight[i]))

Submission status: Wrong Answer

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
重み付きunionfindを使う
https://qiita.com/drken/items/cce6fc5c579051e64fab
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)           
            self.parent[x] = self.find(self.parent[x])      #親の置き換え(圧縮)
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def calc_weight(self, x):
        self.find(x) #圧縮
        return self.weight[x]


    def weighted_union(self, x, y, w):
        wx = self.calc_weight(x)
        wy = self.calc_weight(y)
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if x == y: return 0
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.weight[x] = w - wx + wy
        else:
            self.parent[y] = x
            self.weight[y] = w + wx - wy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        return 0


    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
infos = []
for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        if d == (uf.weight[r]-uf.weight[l]):
            continue
        else:
            print("No")
            exit()
print("Yes")
# for i in uf.parent.keys():
#     print("index:{} rank:{}, parent:{}, weight:{}".format(i,uf.rank[i],uf.parent[i],uf.weight[i]))

Submission status: Wrong Answer

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
"""

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            self.par[x] = self.find(self.par[x]) #根を置き換えていく
            return self.par[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        self.par[x] = y
    
    # 判定
    def judge(self,x,y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
seen = [0] * (N+1)
infos = []
for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l,r):
        # 左が既出の場合 : 右の情報を追加
        uf.union(l,r)
        if seen[l] and not seen[r]:
            uf.rank[r] = uf.rank[l] + d
            seen[r] = True
        elif seen[r] and not seen[l]:
            uf.rank[l] = uf.rank[r] - d
            seen[l] = True
        else:
            uf.rank[r] = uf.rank[l] + d
            seen[r] = seen[l] = True
    # 二回目のやつらは後で拘束条件に使う
    else:
        # print("l:{},r:{}".format(uf.rank[l],uf.rank[r]))
        if uf.rank[r] - uf.rank[l] == d:
            continue
        else:
            print("No")
            exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
if n==1 or m==0:print("Yes");exit()
lst=[float("inf") for i in range(n+1)]
a,b,c=map(int,input().split())
lst[a]=0
lst[b]=c
l=[list(map(int,input().split())) for _ in range(m-1)]
for i in l:
    if lst[i[1]]==float("inf"):
        lst[i[1]]=lst[i[0]]+i[2]
    elif lst[i[1]]!=lst[i[0]]+i[2]:
        print("No");exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
#重み付きUnion-Find
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)

n,m = map(int,input().split())

#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0
par = [-1]*(n+1)
wei = [0]*(n+1)

ans=True
for i in range(m):
    p=[int(j) for j in input().split()]
    unite(p[0],p[1],p[2])
    if same(p[0],p[1]):
        if diff(p[0],p[1])!=p[2]:
            ans=False

if ans:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

n,m=map(int,input().split())
u=WeightedUnionFind(n)
ans=True
for i in range(m):
    p=[int(j) for j in input().split()]
    u.union(p[0],p[1],p[2])
    if u.same(p[0],p[1]):
        if u.diff(p[0],p[1])!=p[2]:
            ans=False
    print(u.diff(p[0],p[1]))
if ans:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
lrd=[]
from collections import Counter
l=Counter()
ans=True
q=1
r=set()
def f(q):
    while True:
        if q in r:
            q+=1
        else:
            break
    return q
for i in range(m):
    p=[int(j) for j in input().split()]
    lrd.append((p[0],p[1],p[2]))
    if l[p[0]]==0:
        if l[p[1]]==0:
            q=f(q)
            l[p[0]]=q
            l[p[1]]=p[2]+q
            r.add(l[p[0]])
            r.add(l[p[1]])
        else:
            l[p[0]]=l[p[1]]-p[2]
            if l[p[0]] in r:
                ans=False
            else:
                r.add(l[p[0]])
    else:
        if l[p[1]]==0:
            l[p[1]]=l[p[0]]+p[2]
            if l[p[1]] in r:
                ans=False
            else:
                r.add(l[p[1]])
        else:
            if l[p[0]]+p[2]!=l[p[1]]:
                ans=False
            
if ans:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def main():
  n, m = map(int,input().split())
  LRD = [list(map(int,input().split())) for _ in range(m)]

  dif = [0]*(n+1)
  ans = "Yes"
  tmp = 1
  for i, (L, R, D) in enumerate(LRD):
    if L > R:
      L, R = R, L
    if i == 0:
      dif[L] = tmp
      dif[R] = tmp + D
      tmp += D
    else:
      if dif[L] != 0 and dif[R] != 0:
        if dif[R] - dif[L] != D:
          ans = "No"
          break
      elif dif[L] != 0 and dif[R] == 0:
        dif[R] = dif[L] + D
      elif dif[L] == 0 and dif[R] != 0:
        dif[L] = dif[R] - D
      else:
        dif[L] = tmp
        dif[R] = tmp + D
        tmp += D
  print(ans)

main()

Submission status: Wrong Answer

Solution code:
def main():
  n, m = map(int,input().split())
  LRD = [list(map(int,input().split())) for _ in range(m)]

  dif = [0]*(n+1)
  ans = "Yes"
  for i, (L, R, D) in enumerate(LRD):
    if L > R:
      L, R = R, L
    if i == 0:
      dif[L] = 1
      dif[R] = 1 + D
    else:
      if dif[L] != 0 and dif[R] != 0:
        if dif[R] - dif[L] != D:
          ans = "No"
          break
      elif dif[L] != 0 and dif[R] == 0:
        dif[R] = dif[L] + D
      elif dif[L] == 0 and dif[R] != 0:
        dif[L] = dif[R] - D
  print(ans)

main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(M)]
lst = []
for i in range(N):
	lst.append([i,0])

def pos(i):
	if lst[X[i][0]-1][0] != lst[X[i][1]-1][0]:
		lst[X[i][1]-1][0] = lst[X[i][0]-1][0]
		lst[X[i][1]-1][1] = lst[X[i][0]-1][1] + X[i][2]
	else:
		if lst[X[i][1]-1][1] - lst[X[i][0]-1][1] != X[i][2]:
			print("No")
			exit()

for i in range(M):
	pos(i)
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

N,M=map(int,input().split())
L=[0 for i in range(N+1)]
P=[i for i in range(N+1)]
D=[10**16 for i in range(N+1)]
C=[0 for i in range(N+1)]

A=dict()
B=[[]for i in range(N+1)]
for i in range(M):
    l,r,d=map(int,input().split())
    A[l,r,d]=1
    B[l].append([r,d])
    C[r]=1

Q=[]
for i in range(1,N+1):
    if C[i]==0:
        Q.append(i)
        D[i]=0
import heapq
#print(Q)
for i in Q:
    q=[]
    heapq.heapify(q)
    for x,y in B[i]:
        heapq.heappush(q,[y,x,i])
    #print(B)
    for j in range(10**6):
        if len(q)==0:
            break
        else:
            X,Y,Z=q[0]
            D[Y]=X
            for k in B[Y]:
                if D[k[0]]>D[Y]+k[1]:
                    heapq.heappush(q,[D[Y]+k[1],k[0],Y])
            heapq.heappop(q)
#print(D)

for i,j,k in A:
    if D[j]-D[i]!=k:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
lrd=[]
for i in range(m):
    lrd.append([int(j) for j in input().split()])
from operator import itemgetter
lrd.sort(key=itemgetter(0))
l=[-1 for i in range(n+1)]
p=0
q=set()
for i in range(m):
    if l[lrd[i][0]]==-1:
        k=1
        while True:
            if p+k not in q:
                p+=k
                break
            k+=1
        l[lrd[i][0]]=p
        if l[lrd[i][1]]==-1:
            l[lrd[i][1]]=l[lrd[i][0]]+lrd[i][2]
        else:
            if l[lrd[i][1]]!=l[lrd[i][0]]+lrd[i][2]:
                print("No")
                exit()
    else:
        if l[lrd[i][1]]==-1:
            l[lrd[i][1]]=l[lrd[i][0]]+lrd[i][2]
        else:
            if l[lrd[i][1]]!=l[lrd[i][0]]+lrd[i][2]:
                print("No")
                exit()
print("Yes")