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:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return root_x

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    if root_x == root_y:
        return
    if rank[root_x] >= rank[root_y]:
        nodes[y] = root_x
        diff_weight[y] = w + weight(x) - weight(y)
        if rank[root_x] == rank[root_y]:
            rank[x] += 1
    else:
        nodes[x] = root_y
        diff_weight[x] = -w + weight(y) - weight(x)

def same(x,y):
    return root(x) == root(y)

def diff(x,y):
    return weight(y) - weight(x)

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    if same(L,R) is False:
        unite(L,R,D)
    elif diff(L,R) != D:
        ans = "No"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return root_x

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    if root_x == root_y:
        return
    if rank[root_x] >= rank[root_y]:
        nodes[y] = root_x
        diff_weight[y] = w + weight(x) - weight(y)
        if rank[root_x] == rank[root_y]:
            rank[x] += 1
    else:
        nodes[x] = root_y
        diff_weight[x] = -w + weight(y) - weight(x)

def same(x,y):
    return root(x) == root(y)

def diff(x,y):
    return weight(y) - weight(x)

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    if same is False:
        unite(L,R,D)
    elif diff(L,R) != D:
        ans = "No"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return root_x

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    if root_x == root_y:
        return
    if rank[root_x] >= rank[root_y]:
        nodes[y] = root_x
        diff_weight[y] = w + weight(x) - weight(y)
        if rank[root_x] == rank[root_y]:
            rank[x] += 1
    else:
        nodes[x] = root_y
        diff_weight[x] = -w + weight(y) - weight(x)

def diff(x,y):
    return weight(y) - weight(x)

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)

for L,R,D in info:
    L -= 1; R -= 1
    if diff(L,R) != D:
        ans = "No"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    nodes[x] = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    return nodes[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    if root_x == root_y:
        return
    if rank[root_x] > rank[root_y]:
        nodes[y] = root_x
        diff_weight[y] = w + weight(x) - weight(y)
    elif rank[root_x] == rank[root_y]:
        nodes[y] = root_x
        diff_weight[y] = w + weight(x) - weight(y)
        rank[x] += 1
    else:
        nodes[x] = root_y
        diff_weight[x] = -w + weight(y) - weight(x)

def weight(x):
    root(x)
    return diff_weight[x]

def diff(x,y):
    return weight(y) - weight(x)

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)

for L,R,D in info:
    L -= 1; R -= 1
    if diff(L,R) != D:
        ans = "No"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 経路圧縮:再帰的に根を調べてその過程で通った要素は全て根に直接つなぎ直す
        nodes[x] = root(nodes[x])
        # 根に近いものから親の重みを足す. これがxを根に直接繋いだ時の重みになる
        diff_weight[x] += diff_weight[nodes[x]]
        return nodes[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    # 根が同じならreturn (自己ループを考慮)
    if root_x == root_y:
        return
    #根ノードは木の高さを表す(負数で表していることに注意)
    rank_x = -nodes[root_x]; rank_y = -nodes[root_y]
    if rank_x >= rank_y:
        root_l = root_x; root_s = root_y
        l = x; s = y
    else:
        root_l = root_y; root_s = root_x
        l = y; s = x
        w *= -1
    # 低い木を高い木に繋げる
    nodes[root_s] = root_l
    # ２つの木の高さが同じなら繋げた後は高さが1だけ高くなる
    if rank_x == rank_y:
        nodes[root_l] -= 1
    # 繋ぎ直す時の重みの変更
    diff_weight[root_s] = w - weight(s) + weight(l)

# 差分重みの累積和をとることでxの重みが分かる
def weight(x):
    root(x)
    return diff_weight[x]

# xからyへの重み
def diff(x,y):
    return weight(y) - weight(x)

# ノードは-1で初期化, Nは頂点数
nodes = [-1]*N
# ウェイトは0で初期化, Nは頂点数
diff_weight = [0]*N

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    if root(L) == root(R):
        if diff(L,R) != D:
            ans = "No"
            break
        else:
            pass
    else:
        unite(L,R,D)

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 経路圧縮:再帰的に根を調べてその過程で通った要素は全て根に直接つなぎ直す
        nodes[x] = root(nodes[x])
        # 根に近いものから親の重みを足す. これがxを根に直接繋いだ時の重みになる
        diff_weight[x] += diff_weight[nodes[x]]
        return nodes[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    # 根が同じならreturn (自己ループを考慮)
    if root_x == root_y:
        return
    #根ノードは木の高さを表す(負数で表していることに注意)
    rank_x = -nodes[root_x]; rank_y = -nodes[root_y]
    if rank_x >= rank_y:
        root_l = root_x; root_s = root_y
        l = x; s = y
    else:
        root_l = root_y; root_s = root_x
        l = y; s = x
        w *= -1
    # 低い木を高い木に繋げる
    nodes[root_s] = root_l
    # ２つの木の高さが同じなら繋げた後は高さが1だけ高くなる
    if rank_x == rank_y:
        nodes[root_l] -= 1
    # 繋ぎ直す時の重みの変更
    diff_weight[root_s] = w - weight(s) + weight(l)

# 差分重みの累積和をとることでxの重みが分かる
def weight(x):
    root(x)
    return diff_weight[x]

# xからyへの重み
def diff(x,y):
    return weight(y) - weight(x)

# ノードは-1で初期化, Nは頂点数
nodes = [-1]*N
# ウェイトは0で初期化, Nは頂点数
diff_weight = [0]*N

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)

for L,R,D in info:
    L -= 1; R -= 1
    if diff(L,R) != D:
        ans = "No"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        parent = root(nodes[x])
        # 親の重みの累積和をとる. これがxを根に直接繋いだ時の重みになる
        weight[x] += weight[nodes[x]]
        # 経路圧縮:再帰的に根を調べてその過程で通った要素は全て根に直接つなぎ直す
        nodes[x] = parent
        return parent

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    # 根が同じならreturn (自己ループを考慮)
    if root_x == root_y:
        return
    #根ノードは木の高さを表す(負数で表していることに注意)
    rank_x = -nodes[root_x]; rank_y = -nodes[root_y]
    if rank_x >= rank_y:
        root_l = root_x; root_s = root_y
        l = x; s = y
    else:
        root_l = root_y; root_s = root_x
        l = y; s = x
        w *= -1
    # 低い木を高い木に繋げる
    nodes[root_s] = root_l
    # ２つの木の高さが同じなら繋げた後は高さが1だけ高くなる
    if rank_x == rank_y:
        nodes[root_l] -= 1
    # 繋ぎ直す時の重みの変更
    weight[root_s] = w - weight[s] + weight[l]

# xからyへの重み
def diff(x,y):
    return weight[y] - weight[x]

# ノードは-1で初期化, Nは頂点数
nodes = [-1]*N
# ウェイトは0で初期化, Nは頂点数
weight = [0]*N

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)

for L,R,D in info:
    L -= 1; R -= 1
    if diff(L,R) != D:
        ans = "No"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        parent = root(nodes[x])
        # 親の重みの累積和をとる. これがxを根に直接繋いだ時の重みになる
        weight[x] += weight[nodes[x]]
        # 経路圧縮:再帰的に根を調べてその過程で通った要素は全て根に直接つなぎ直す
        nodes[x] = parent
        return parent

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    # 根が同じならreturn (自己ループを考慮)
    if root_x == root_y:
        return
    #根ノードは木の高さを表す(負数で表していることに注意)
    rank_x = -nodes[root_x]; rank_y = -nodes[root_y]
    if rank_x >= rank_y:
        root_l = root_x; root_s = root_y
        l = x; s = y
    else:
        root_l = root_y; root_s = root_x
        l = y; s = x
        w *= -1
    # 繋いだ分だけ木を高くする
    nodes[root_l] += nodes[root_s]
    # 低い木を高い木に繋げる
    nodes[root_s] = root_l
    # 繋ぎ直す時の重みの変更
    weight[root_s] = w - weight[s] + weight[l]

# xからyへの重み
def diff(x,y):
    return weight[y] - weight[x]

# ノードは-1で初期化, Nは頂点数
nodes = [-1]*N
# ウェイトは0で初期化, Nは頂点数
weight = [0]*N

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)

for L,R,D in info:
    L -= 1; R -= 1
    if diff(L,R) != D:
        ans = "No"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        parent = nodes[x]
        # 経路圧縮:再帰的に根を調べてその過程で通った要素は全て根に直接つなぎ直す
        nodes[x] = root(nodes[x])
        # 親の重みの累積和をとる. これがxを根に直接繋いだ時の重みになる
        weight[x] += weight[parent]
        return nodes[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    # 根が同じならreturn (自己ループを考慮)
    if root_x == root_y:
        return
    #根ノードは木の高さを表す(負数で表していることに注意)
    rank_x = -nodes[root_x]; rank_y = -nodes[root_y]
    if rank_x >= rank_y:
        root_l = root_x; root_s = root_y
        l = x; s = y
    else:
        root_l = root_y; root_s = root_x
        l = y; s = x
        w *= -1
    # 繋いだ分だけ木を高くする
    nodes[root_l] += nodes[root_s]
    # 低い木を高い木に繋げる
    nodes[root_s] = root_l
    # 繋ぎ直す時の重みの変更
    weight[root_s] = w - weight[s] + weight[l]

# xからyへの重み
def diff(x,y):
    return weight[y] - weight[x]

# ノードは-1で初期化, Nは頂点数
nodes = [-1]*N
# ウェイトは0で初期化, Nは頂点数
weight = [0]*N

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)

for L,R,D in info:
    L -= 1; R -= 1
    if diff(L,R) != D:
        ans = "No"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 親の重みの累積和をとる. これがxを根に直接繋いだ時の重みになる
        weight[x] += weight[nodes[x]]
        # 経路圧縮:再帰的に根を調べてその過程で通った要素は全て根に直接つなぎ直す
        nodes[x] = root(nodes[x])
        return nodes[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    #根ノードは木の高さを表す(負数で表していることに注意)
    rank_x = -nodes[root_x]; rank_y = -nodes[root_y]
    if rank_x >= rank_y:
        root_l = root_x; root_s = root_y
        l = x; s = y
    else:
        root_l = root_y; root_s = root_x
        l = y; s = x
        w *= -1
    # 繋いだ分だけ木を高くする
    nodes[root_l] += nodes[root_s]
    # 低い木を高い木に繋げる
    nodes[root_s] = root_l
    # 繋ぎ直す時の重みの変更
    weight[root_s] = w - weight[s] + weight[l]

# 根が同じ->True
def same(x,y):
    return root(x) == root(y)

# xからyへの重み
def diff(x,y):
    return weight[y] - weight[x]

# ノードは-1で初期化, Nは頂点数
nodes = [-1]*N
# ウェイトは0で初期化, Nは頂点数
weight = [0]*N
ans = "Yes"
for L,R,D in info:
    L -= 1; R -= 1
    if same(L,R):
        if diff(L,R) != D:
            ans = "No"
            break
        else:
            pass
    else:
        unite(L,R,D)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 経路圧縮:再帰的に根を調べてその過程で通った要素は全て根に直接つなぎ直す
        nodes[x] = root(nodes[x])
        # 親の重みの累積和をとる. これがxを根に直接繋いだ時の重みになる
        weight[x] += weight[nodes[x]]
        return nodes[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    # 根が同じなら結合済みなのでreturn(わざわざ分岐するのは自己ループを考慮)
    if root_x == root_y:
        return
    #根ノードは木の高さを表す(負数で表していることに注意)
    rank_x = -nodes[root_x]; rank_y = -nodes[root_y]
    if rank_x >= rank_y:
        root_l = root_x; root_s = root_y
        l = x; s = y
    else:
        root_l = root_y; root_s = root_x
        l = y; s = x
        w *= -1
    # 繋いだ分だけ木を高くする
    nodes[root_l] += nodes[root_s]
    # 低い木を高い木に繋げる
    nodes[root_s] = root_l
    # 繋ぎ直す時の重みの変更
    weight[root_s] = w - weight[s] + weight[l]

# 根が同じ->True
def same(x,y):
    return root(x) == root(y)

# xからyへの重み
def diff(x,y):
    return weight[y] - weight[x]

# ノードは-1で初期化, Nは頂点数
nodes = [-1]*N
# ウェイトは0で初期化, Nは頂点数
weight = [0]*N
ans = "Yes"
for L,R,D in info:
    L -= 1; R -= 1
    if same(L,R) is True and diff(L,R) != D:
        ans = "No"
        break
    unite(L,R,D)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 経路圧縮:再帰的に根を調べてその過程で通った要素は全て根に直接つなぎ直す
        nodes[x] = root(nodes[x])
        # 親の重みの累積和をとる. これがxを根に直接繋いだ時の重みになる
        weight[x] += weight[nodes[x]]
        return nodes[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    # 根が同じなら結合済みなのでreturn(わざわざ分岐するのは自己ループを考慮)
    if root_x == root_y:
        return
    #根ノードは木の高さを表す(負数で表していることに注意)
    rank_x = -nodes[root_x]; rank_y = -nodes[root_y]
    if rank_x >= rank_y:
        root_l = root_x; root_s = root_y
        l = x; s = y
    else:
        root_l = root_y; root_s = root_x
        l = y; s = x
        w *= -1
    # 繋いだ分だけ木を高くする
    nodes[root_l] += nodes[root_s]
    # 低い木を高い木に繋げる
    nodes[root_s] = root_l
    # 繋ぎ直す時の重みの変更
    weight[root_s] = w - weight[s] + weight[l]

# xからyへの重み
def diff(x,y):
    return weight[y] - weight[x]

# ノードは-1で初期化, Nは頂点数
nodes = [-1]*N
# ウェイトは0で初期化, Nは頂点数
weight = [0]*N
ans = "Yes"
for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)

for L,R,D in info:
    L -= 1; R -= 1
    if diff(L,R) != D:
        ans = "No"
        break
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 経路圧縮:再帰的に根を調べてその過程で通った要素は全て根に直接つなぎ直す
        nodes[x] = root(nodes[x])
        # 親の重みの累積和をとる. これがxを根に直接繋いだ時の重みになる
        weight[x] += weight[nodes[x]]
        return nodes[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    # 根が同じなら結合済みなのでreturn(わざわざ分岐するのは自己ループを考慮)
    if root_x == root_y:
        return
    #根ノードは木の高さを表す(負数で表していることに注意)
    rank_x = -nodes[root_x]; rank_y = -nodes[root_y]
    if rank_x >= rank_y:
        root_l = root_x; root_s = root_y
        l = x; s = y
    else:
        root_l = root_y; root_s = root_x
        l = y; s = x
    # 繋いだ分だけ木を高くする
    nodes[root_l] += nodes[root_s]
    # 低い木を高い木に繋げる
    nodes[root_s] = root_l
    # 繋ぎ直す時の重みの変更
    weight[root_s] = w - weight[s] + weight[l]

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

# ノードは-1で初期化, Nは頂点数
nodes = [-1]*N
# ウェイトは0で初期化, Nは頂点数
weight = [0]*N
ans = "Yes"
for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)

for L,R,D in info:
    L -= 1; R -= 1
    if diff(L,R) != D:
        ans = "No"
        break
print(ans)

Submission status: Wrong Answer

Solution code:
class vertex : 
    def __init__(self) : 
        self.edges = []

    def add_edge(self, u, weight) : 
        self.edges.append((u, weight))


def dfs(graph, V, s) : 
    travelled = [0 for _ in xrange(V)]
    
    for node in s : 
        if travelled[node] : 
            continue
        
        stack = []
        stack.append((node, 0))

        while stack : 
            index, full_weight = stack.pop()

            for dst, weight in graph[index].edges :
                if travelled[dst] :
                    if travelled[dst] != travelled[index] + weight : 
                        return False
                    continue
                
                travelled[dst] = travelled[index] + weight
                stack.append((dst, travelled[index] + weight))
    
    return True


V, E = map(int, raw_input().strip().split(' '))

graph = [vertex() for _ in xrange(V)]

memo  = [False for _ in xrange(V)]
s     = set([])
for _ in xrange(E) : 
    l, r, d = map(int, raw_input().strip().split(' '))
    l -= 1
    r -= 1
    graph[l].add_edge(r, d)
    memo[r] = True
    s.add(l)
    s.add(r)


if dfs(graph, V, s) :
    print "Yes"
else : 
    print "No"

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M = map(int,input().split())

graph = [[] for i in range(N)]
flag = 1
for i in range(M):
    L,R,D = map(int,input().split())
    graph[L-1].append([R-1,D])
    graph[R-1].append([L-1,-D])

#print(graph)
x = [None for i in range(N)]

def f():
    for i in range(N):
        if x[i] == None:
            x[i] = 0
            q = deque([i])
            while len(q):
                j = q.popleft()
                for k,d in graph[j]:
                    if x[k] == None:
                        q.append(k)
                        x[k] = x[j]+d
                    elif x[k] == x[j]+d:
                        return False
                        
    return True

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())

info = {}
flag = 1
for i in range(M):
    L,R,D = input().split()
    D = int(D)
    if L not in info and R not in info:
        info[L] = 0
        info[R] = D
    elif R not in info:
        info[R] = info[L] + D
    elif L not in info:
        info[L] = info[R]-D
    else:
        if info[R]-info[L] != D:
            flag = 0


if flag ==1:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
class UnionFind:
    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 is_same(self,x,y):
        return self.find(x)==self.find(y)

    def union(self,x,y,w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry   
        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 diff(self,x,y):
        return self.weight[x] - self.weight[y]


N,M = list(map(int,input().split()))
un = UnionFind(N)

for i in range(M):
    l,r,w = list(map(int,input().split()))
    if un.is_same(l,r):
        diff = un.diff(l,r)
        if diff != w:
            print('No')
            exit()
    else:
        un.union(l,r,w)

print('Yes')

Submission status: Wrong Answer

Solution code:
class UnionFind:
    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 is_same(self,x,y):
        return self.find(x)==self.find(y)

    def union(self,x,y,w):
        rx = self.find(x)
        ry = self.find(y)
        if (rx == ry):return 
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry   
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[x] += 1
    def diff(self,x,y):
        if self.is_same(x,y) == False :return 
        return self.weight[x] - self.weight[y]


N,M = list(map(int,input().split()))
data = []
un = UnionFind(N)

for i in range(M):
    l,r,w = list(map(int,input().split()))
    if un.is_same(l,r) == False:
        un.union(l,r,w)
    elif un.diff(l,r) != w:
        print('No')
        exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    tmpl, tmpr, tmpd = map(int, input().split())
    G[tmpl].append((tmpr, tmpd))
    G[tmpr].append((tmpl, -tmpd))

field = [None] * (N+1)


def dfs(i):
    ret = True
    for elem in G[i]:
        if field[elem[0]] is not None:
            if field[elem[0]] != field[i]+elem[1]:
                return False
            continue
        else:
            field[elem[0]] = field[i]+elem[1]
            ret = dfs(elem[0])
    return ret


for i in range(1, N+1):
    if field[i] is None:
        field[i] = 0
        if not dfs(i):
            print('No')
            exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    tmpl, tmpr, tmpd = map(int, input().split())
    G[tmpl].append((tmpr, tmpd))
    G[tmpr].append((tmpl, -tmpd))

field = [None] * (N+1)


def dfs(i):
    for elem in G[i]:
        if field[elem[0]] is not None:
            if field[elem[0]] != field[i]+elem[1]:
                return False
            continue
        else:
            field[elem[0]] = field[i]+elem[1]
            dfs(elem[0])
    return True


for i in range(1, N+1):
    if field[i] is None:
        field[i] = 0
        if not dfs(i):
            print('No')
            exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

def root(x):
  if x == par[x]:
    return x
  r = root(par[x])
  dis[x] += dis[par[x]]
  par[x] = r
  return r

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  rootl, rootr = root(l), root(r)
  if rootl != rootr:
    # lをrにマージする
    if r == rootr:
      dis[rootl] = d - cost(l)
    else:
      dis[rootl] = d - (dis[l] - dis[r]) # (cost(l) - cost(r))
    par[rootl] = r
  else:
    # コストが同じかどうか
    if d == cost(l) - cost(r):
      continue
    else:
      print("No")
      exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

def root(x):
  if x == par[x]:
    return x
  r = root(par[x])
  dis[x] += dis[par[x]]
  par[x] = r
  return r

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  rootl, rootr = root(l), root(r)
  if rootl != rootr:
    # lをrにマージする
    if r == rootr:
      dis[rootl] = d - cost(l)
    else:
      dis[rootl] = d - (cost(l) - cost(r))
    par[rootl] = r
  else:
    # コストが同じかどうか
    if d == cost(l) - cost(r):
      continue
    else:
      print("No")
      exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

def root(x):
  if x == par[x]:
    return x
  r = root(par[x])
  dis[x] += dis[par[x]]
  par[x] = r
  return r

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  rootl, rootr = root(l), root(r)
  if rootl != rootr:
    # lをrにマージする
    if r == rootr:
      dis[rootl] = d - cost(l)
    else:
      dis[rootl] = d - (cost(l) - cost(r))
    par[rootl] = r
  else:
    # コストが同じかどうか
    if d == dis[l] - dis[r]:
      continue
    else:
      print("No")
      exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

def root(x):
  if x == par[x]:
    return x
  r = root(par[x])
  dis[x] += dis[par[x]]
  par[x] = r
  return r

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(dis[par[x]])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  rootl, rootr = root(l), root(r)
  if rootl != rootr:
    # lをrにマージする
    if r == rootr:
      dis[rootl] = d - cost(l)
    else:
      dis[rootl] = d - (cost(l) - cost(r))
    par[rootl] = r
  else:
    # コストが同じかどうか
    if d == dis[l] - dis[r]:
      continue
    else:
      print("No")
      exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]

def root(x):
  if x == par[x]:
    return x
  r = root(par[x])
  dist[x] += dist[par[x]]
  par[x] = r
  return r

def direct_cost(x):
  if x == par[x]:
    return 0
  return dist[x] + direct_cost(par[x])

def diff(x, y):
  return direct_cost(x) - direct_cost(y)

flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  rootx, rooty = root(l), root(r)
  if rootx != rooty:
    if r != rooty:
      # 直接yにつなげる
      dist[rootx] = d - direct_cost(l)
    else:
      # yの根につなげる
      dist[rootx] = d - (dist[l] - dist[r])
    par[rootx] = l
  else:
    if d != diff(l, r):
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(dist)]
print()
"""

print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]

def root(x):
  if x == par[x]:
    return x
  r = root(par[x])
  dist[x] += dist[par[x]]
  par[x] = r
  return r

def direct_cost(x):
  if x == par[x]:
    return 0
  return dist[x] + direct_cost(par[x])
  
def diff(x, y):
  return direct_cost(x) - direct_cost(y)

flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  rootx, rooty = root(l), root(r)
  if rootx != rooty:
    if r != rooty:
      # 直接yにつなげる
      dist[rootx] = d - direct_cost(l)
    else:
      # yの根につなげる
      dist[rootx] = d - (dist[l] - dist[r])
    par[rootx] = rooty
  else:
    if d != diff(l, r):
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(dist)]
print()
"""

print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]

def root(x):
  if x == par[x]:
    return x
  r = root(par[x])
  dist[x] += direct_cost(par[x])
  par[r] = r
  return r

def direct_cost(x):
  if x == par[x]:
    return 0
  return dist[x] + direct_cost(par[x])
  
def diff(x, y):
  return dist[x] - dist[y]

flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  rootx, rooty = root(l), root(r)
  if rootx != rooty:
    dist[rootx] = d
    par[rootx] = rooty
  else:
    if d != diff(l, r):
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(dist)]
print()
"""

print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
lrd = []
for i in range(M):
    l, r, d = map(int, input().split())
    lrd.append([l, r, d])
lrd.sort()

position = [float("inf") for _ in range(2*10**6+2)]
for i in range(M):
    l, r, d = lrd[i]

    if position[l] == float("inf") and position[r] == float("inf"):
        position[l] = 0
        position[r] = d
    else:
        if position[l] != float("inf") and position[r] != float("inf"):
            p_r = position[r]
            p_l = position[l]
            if p_r - p_l != d:
                print("No")
                exit()
        elif position[l] != float("inf"):
            p_l = position[l]
            position[r] = position[l] + d
        elif position[r] != float("inf"):
            p_r = position[r]
            position[l] = position[r] - d

print("Yes")