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:
print('Yes')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
par = [i for i in range(n)]
diff = [0] * n


def find(x):
    if par[x] == x:
        return x, 0
    else:
        a, b = find(par[x])
        par[x] = a
        diff[x] += b
        return a, diff[x]


def unite(x, y, z):
    s, ws = find(x)
    t, wt = find(y)
    # print(ws, wt)
    if s == t:
        if ws - wt == z:
            pass
        else:
            print('No')
            exit(0)
    else:
        if ws < z + wt:
            par[s] = t
            diff[s] = z + wt - ws
        else:
            par[t] = s
            diff[s] = ws - z - wt


for _ in range(m):
    l, r, d = map(int, input().split())
    unite(l - 1, r - 1, d)

print('Yes')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
par = [i for i in range(n)]
diff = [0]*n

def find(x):
    if par[x] == x:
        return x, 0
    else:
        a, b = find(par[x])
        par[x] = a
        diff[x] += b
        return a, diff[x]


def unite(x,y,z):
    s, ws = find(x)
    t, wt = find(y)
    #print(ws, wt)
    if ws<z+wt:
        par[s] = t
        diff[s] = z+wt-ws
    else:
        par[t] = s
        diff[s] = ws -z-wt

unites =[]

for _ in range(m):
    l,r,d = map(int, input().split())
    unites.append((l,r,d))
    unite(l-1,r-1,d)
    #print(diff)
    #print(par)

for x, y, z in unites:
    s, ws = find(x-1)
    t, wt = find(y-1)
    #print(ws, wt, z)
    if s==t:
        if ws != wt +z:
            print('No')
            exit(0)

print('Yes')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
par = [i for i in range(n)]
diff = [0]*n

def find(x):
    if par[x] == x:
        return x, 0
    else:
        a, b = find(par[x])
        par[x] = a
        diff[x] += b
        return a, diff[x]


def unite(x,y,z):
    s, ws = find(x)
    t, wt = find(y)
    #print(ws, wt)
    if s==t:
        if ws - wt == z:
            pass
        else:
            print('No')
            exit(0)
    else:
        if ws<z+wt:
            par[s] = t
            diff[s] = z+wt-ws
        else:
            par[t] = s
            diff[s] = ws -z-wt

unites =[]

for _ in range(m):
    l,r,d = map(int, input().split())
    unites.append((l,r,d))
    unite(l-1,r-1,d)
    #print(diff)
    #print(par)

for x, y, z in unites:
    s, ws = find(x-1)
    t, wt = find(y-1)
    #print(ws, wt, z)
    if s==t:
        if ws != wt +z:
            print('No')
            exit(0)

print('Yes')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
par = [i for i in range(n)]
diff = [0]*n

def find(x):
    if par[x] == x:
        return x, 0
    else:
        a, b = find(par[x])
        par[x] = a
        diff[x] += b
        return a, diff[x]


def unite(x,y,z):
    s, ws = find(x)
    t, wt = find(y)
    #print(ws, wt)
    if s==t:
        if ws - wt == z:
            pass
        else:
            print('No')
            exit(0)
    else:
        par[s] = t
        diff[s] = z

unites =[]

for _ in range(m):
    l,r,d = map(int, input().split())
    unites.append((l,r,d))
    unite(l-1,r-1,d)
#print(unites)

for x, y, z in unites:
    unite(x-1, y-1, d)

print('Yes')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
par = [i for i in range(n)]
diff = [0]*n

def find(x):
    if par[x] == x:
        return x, 0
    else:
        a, b = find(par[x])
        par[x] = a
        diff[x] += b
        return a, diff[x]


def unite(x,y,z):
    s, ws = find(x)
    t, wt = find(y)
    #print(ws, wt)
    if s==t:
        if ws - wt == z:
            pass
        else:
            print('Yes')
            exit(0)
    else:
        par[s] = t
        diff[s] = z

for _ in range(m):
    l,r,d = map(int, input().split())
    unite(l-1,r-1,d)

print('No')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
par = [i for i in range(n)]
diff = [0]*n

def find(x):
    if par[x] == x:
        return x, 0
    else:
        a, b = find(par[x])
        par[x] = a
        diff[x] += b
        return a, diff[x]


def unite(x,y,z):
    s, ws = find(x)
    t, wt = find(y)
    #print(ws, wt)
    if s==t:
        if ws - wt == z:
            pass
        else:
            print('No')
            exit(0)
    else:
        par[s] = t
        diff[s] = z

for _ in range(m):
    l,r,d = map(int, input().split())
    unite(l-1,r-1,d)

print('Yes')

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0]*size
        self.diff_weight = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        r = self.find(self.parent[x])
        self.parent[x] = r
        self.diff_weight[x] += self.diff_weight[r]
        return r
    
    def unite(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.parent[y] = x
        self.diff_weight[y] = w

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def weight(self, x):
        self.find(x)
        return self.diff_weight[x]

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

N, M = map(int,input().split())
uf = WeightedUnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    l -= 1
    r -= 1
    if uf.same(l,r) and uf.diff(l,r) != d:
        print("No")
        exit()
    uf.unite(l,r,d)
print("Yes")

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0]*size
        self.diff_weight = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        r = self.find(self.parent[x])
        self.parent[x] = r
        self.diff_weight[x] += self.diff_weight[r]
        return r
    
    def unite(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        elif self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.parent[y] = x
        self.diff_weight[y] = w

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def weight(self, x):
        self.find(x)
        return self.diff_weight[x]

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

N, M = map(int,input().split())
uf = WeightedUnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    l -= 1
    r -= 1
    if uf.same(l,r) and uf.diff(l,r) != d:
        print("No")
        exit()
    uf.unite(l,r,d)
print("Yes")

Submission status: Wrong Answer

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

def f(hito, zahyo):
  x[hito]=zahyo
  for tsugi in links[hito]:
    if x[tsugi[0]]==None:
      f(tsugi[0], zahyo+tsugi[1])
    else:
      if x[tsugi[0]]!=zahyo+tsugi[1]:
        return False

N, M=map(int, input().split())
links=[[] for _ in range(N+1)]
for _ in range(M):
  l, r, d=map(int, input().split())
  links[l].append([r, d])
  links[r].append([l, -d])
  
x=[None]*(N+1)
for i in range(1, N+1):
  if x[i]==None and f(i, 0)==False:
    print('No')
    exit()
    
print('Yes')

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque, defaultdict
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    ref = defaultdict(list)
    sta = 0

    for i in range(m):
        a, b, k = map(int, input().split())
        if i == 0:
            sta = a
        g[a].append(b)
        g[b].append(a)
        ref[(a, b)] = k

    q = deque([sta])
    visited = set()
    inf = 10 ** 10
    dist = [-inf] * (n + 1)
    dist[sta] = 1

    while q:
        v = q.pop()
        visited.add(v)
        for x in g[v]:
            if x not in visited:
                if ref[(v, x)] != []:
                    y = ref[(v, x)]
                    if dist[x] == -inf:
                        dist[x] = dist[v] + y
                    elif dist[v] == -inf:
                        dist[v] = dist[x] - y
                    elif dist[x] != dist[v] + y:
                        print("No")
                        exit()
                else:
                    y = ref[(x, v)]
                    if dist[v] == -inf:
                        dist[v] = dist[x] + y
                    elif dist[x] == -inf:
                        dist[x] = dist[v] - y
                    elif dist[v] != dist[x] + y:
                        print("No")
                        exit()
                q.append(x)
    for (i, j), l in ref.items():
        if l == []:
            continue
        elif dist[j] != dist[i] + l:
            print("No")
            exit()
    print("Yes")
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque, defaultdict
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    ref = defaultdict(list)
    sta = 0

    for i in range(m):
        a, b, k = map(int, input().split())
        if i == 0:
            sta = a
        g[a].append(b)
        g[b].append(a)
        ref[(a, b)] = k

    q = deque([sta])
    visited = set()
    inf = 10 ** 9
    dist = [-inf] * (n + 1)
    dist[sta] = 1

    while q:
        v = q.pop()
        visited.add(v)
        for x in g[v]:
            if x not in visited:
                if ref[(v, x)] != []:
                    y = ref[(v, x)]
                    if dist[x] == -inf:
                        dist[x] = dist[v] + y
                    elif dist[v] == -inf:
                        dist[v] = dist[x] - y
                    elif dist[x] != dist[v] + y:
                        print("No")
                        exit()
                else:
                    y = ref[(x, v)]
                    if dist[v] == -inf:
                        dist[v] = dist[x] + y
                    elif dist[x] == -inf:
                        dist[x] = dist[v] - y
                    elif dist[v] != dist[x] + y:
                        print("No")
                        exit()
                q.append(x)
    print("Yes")
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque, defaultdict
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    ref = defaultdict(list)
    sta = 0

    for i in range(m):
        a, b, k = map(int, input().split())
        if i == 0:
            sta = a
        g[a].append(b)
        g[b].append(a)
        ref[(a, b)] = k

    q = deque([sta])
    visited = set()
    dist = [0] * (n + 1)
    dist[sta] = 1

    while q:
        v = q.pop()
        visited.add(v)
        for x in g[v]:
            if x not in visited:
                if ref[(v, x)] != []:
                    y = ref[(v, x)]
                    if not dist[x]:
                        dist[x] = dist[v] + y
                    elif not dist[v]:
                        dist[v] = dist[x] - y
                    elif dist[x] != dist[v] + y:
                        print("No")
                        exit()
                else:
                    y = ref[(x, v)]
                    if not dist[v]:
                        dist[v] = dist[x] + y
                    elif not dist[x]:
                        dist[x] = dist[v] - y
                    elif dist[v] != dist[x] + y:
                        print("No")
                        exit()
                q.append(x)
    print("Yes")
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
"""
unite時に矛盾しないかどうかを判定させる。
同じ木の中では、より右にいるノードを親とする。
親との距離をどこかに記録しておく。
"""
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.dict = [0]*(N+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            u = self.dict[self.parents[x]]
            self.parents[x]=self.find(self.parents[x])
            #xのdictを更新する。
            self.dict[x] += u
            return self.parents[x]
    def unite(self,x,y,d):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            if self.dict[x]-self.dict[y]!=d:
                print("No")
                exit()
        #より右にいるノードを親にする
        if self.dict[y]+d > self.dict[x]:
            self.parents[xRoot] = yRoot
            self.dict[xRoot] = self.dict[y]+d-self.dict[x]
        else:
            self.parents[yRoot] = xRoot
            self.dict[yRoot] = self.dict[x]-(self.dict[y]+d)

N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    tree.unite(l,r,d)
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
import sys
readline = sys.stdin.readline
class UFP():
    def __init__(self, num):
        self.par = [-1]*num
        self.dist = [0]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            res = 0
            xo = x
            while self.par[x] >= 0:
                res = self.dist[x]
                x = self.par[x]
            self.dist[xo] = res
            self.par[xo] = x
            return x
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] > self.par[ry]:
                rx, ry = ry, rx
                x, y = y, x
                d = -d
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
            return True
        else:
            if d + self.dist[x] - self.dist[y]:
                return False
            return True

N, M = map(int, readline().split())
T = UFP(N)
ans = 'No'
for _ in range(M):
    l, r, d = map(int, readline().split())
    l -= 1
    r -= 1
    if not T.union(l, r, d):
        break
else:
    ans = 'Yes'
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
import sys
readline = sys.stdin.readline
class UFP():
    def __init__(self, num):
        self.par = [-1]*num
        self.dist = [0]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            res = 0
            xo = x
            while self.par[x] >= 0:
                res = self.dist[x]
                x = self.par[x]
            self.dist[xo] = res
            return x
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] > self.par[ry]:
                rx, ry = ry, rx
                x, y = y, x
                d = -d
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
            return True
        else:
            if d + self.dist[x] - self.dist[y]:
                return False
            return True

N, M = map(int, readline().split())
T = UFP(N)
ans = 'No'
for _ in range(M):
    l, r, d = map(int, readline().split())
    l -= 1
    r -= 1
    if not T.union(l, r, d):
        break
else:
    ans = 'Yes'
print(ans)

Submission status: Wrong Answer

Solution code:
class UF():
  def __init__(self, N):
    self.parents = [-1] * (N+1)
    self.weight = [0] * (N+1)

  def union(self, f, t, w):
    w += self.weight[f]
    w -= self.weight[t]

    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1
      # w = -w
    self.parents[p1] += self.parents[p2]
    self.weight[p2] = w
    self.parents[p2] = p1

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      y = self.find(self.parents[x])
      self.weight[x] += self.weight[self.parents[x]]
      self.parents[x] = y
      return y

  def compare_weight(self, x, y):
    self.find(x); self.find(y)
    return abs(self.weight[y] - self.weight[x])

  def same(self, n1, n2):
    # import pdb; pdb.set_trace()
    return self.find(n1) == self.find(n2)

N,M = map(int, input().split())
uf = UF(N)
flg = True
for _ in range(M):
  l,r,d = map(int, input().split())
  if uf.same(l, r):
    if uf.compare_weight(l,r) != d:
      flg = False
      break
  else:
    uf.union(l,r,d)

print('Yes') if flg else print('No')

Submission status: Wrong Answer

Solution code:
class UF():
  def __init__(self, N):
    self.parents = [-1] * (N+1)
    self.weight = [0] * (N+1)

  def union(self, f, t, w):
    w += self.weight[f]

    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.weight[p2] += w
    self.parents[p2] = p1

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      y = self.find(self.parents[x])
      self.weight[x] += self.weight[self.parents[x]]
      self.parents[x] = y
      return y

  def compare_weight(self, x, y):
    self.find(x); self.find(y)
    return abs(self.weight[y] - self.weight[x])

  def same(self, n1, n2):
    # import pdb; pdb.set_trace()
    if self.find(n1) != -1 or self.find(n2) != -1:
      return self.find(n1) == self.find(n2)
    return False

N,M = map(int, input().split())
uf = UF(N)
flg = True
for _ in range(M):
  l,r,d = map(int, input().split())
  if uf.same(l, r):
    if uf.compare_weight(l,r) != d:
      flg = False
      break
  else:
    uf.union(l,r,d)

print('Yes') if flg else print('No')

Submission status: Wrong Answer

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

    def find(self, x):
        if self.parent[x] == x:
            return x
        nx = self.find(self.parent[x])
        self.weights[x] += self.weights[self.parent[x]]
        self.parent[x] = nx
        return self.parent[x]

    def unite(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
            self.weights[rx] = d + self.weights[y] - self.weights[x]
        else:
            self.parent[ry] = rx
            self.weights[ry] = - d + self.weights[x] + self.weights[y]
            if self.rank[rx] == self.rank[ry]:
                # rank等しい時はどちらを親にしても良いが，この場合は統合されたxのrankが1増加することに注意する
                self.rank[rx] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def diff(self, x, y):
        return self.weights[x] - self.weights[y]


def main():
    n, m = map(int, input().split())
    wuf = WeightedUnionFind(n)
    for _ in range(m):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1
        if not wuf.same(l, r):
            wuf.unite(l, r, d)
        else:
            if wuf.diff(l, r) != d:
                print("No")
                exit()
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        self.w[x] += self.w[self.parent[x]]
        return self.parent[x]

    def unite(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
            self.w[rx] = d + self.w[y] - self.w[x]
        else:
            self.parent[ry] = rx
            self.w[ry] = - d + self.w[x] + self.w[y]
            if self.rank[rx] == self.rank[ry]:
                # rank等しい時はどちらを親にしても良いが，この場合は統合されたxのrankが1増加することに注意する
                self.rank[rx] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def diff(self, x, y):
        return self.w[x] - self.w[y]


def main():
    n, m = map(int, input().split())
    wuf = WeightedUnionFind(n)
    for _ in range(m):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1
        if not wuf.same(l, r):
            wuf.unite(l, r, d)
        else:
            if wuf.diff(l, r) != d:
                print("No")
                exit()
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):
        return {i for i, x in enumerate(self.parents) if x < 0}


n, m = map(int, input().split())
graph = []
uf = UnionFind(n+1)
for _ in range(m):
    l, r, d = map(int, input().split())
    uf.union(l, r)
    graph.append((l, r, d))

x = {}
ans = "Yes"
re_check = []
# 根の座標を０で確定
for i, y in enumerate(uf.parents):
    if y < 0:
        x[i] = 0

for l, r, d in graph:
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
            break
    elif l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d
    else:
        re_check.append((l, r, d))

for l, r, d in re_check:
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
        continue
    if l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d

if max(x.values()) - min(x.values()) > 10**9:
    ans = "No"

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):
        return {i for i, x in enumerate(self.parents) if x < 0}


n, m = map(int, input().split())
graph = []
uf = UnionFind(n+1)
for _ in range(m):
    l, r, d = map(int, input().split())
    uf.union(l, r)
    graph.append((l, r, d))

x = {}
ans = "Yes"
re_check = []
# 根の座標を０で確定
for i, y in enumerate(uf.parents):
    if y < 0:
        x[i] = 0

for l, r, d in graph:
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
        continue
    if l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d
    else:
        re_check.append((l, r, d))

for l, r, d in re_check:
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
        continue
    if l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d
        
if max(x.values()) - min(x.values()) > 10**9:
    ans = "No"

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):
        return {i for i, x in enumerate(self.parents) if x < 0}


n, m = map(int, input().split())
graph = []
uf = UnionFind(n+1)
for _ in range(m):
    l, r, d = map(int, input().split())
    uf.union(l, r)
    graph.append((l, r, d))

x = {}
ans = "Yes"
# 根の座標を０で確定
for i, y in enumerate(uf.parents):
    if y < 0:
        x[i] = 0

for l, r, d in graph:
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
        continue
    if l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d


print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):
        return {i for i, x in enumerate(self.parents) if x < 0}


n, m = map(int, input().split())
graph = []
uf = UnionFind(n+1)
for _ in range(m):
    l, r, d = map(int, input().split())
    uf.union(l, r)
    graph.append((l, r, d))

x = {0: 0}
ans = "Yes"
# 根の座標を０で確定
for i, y in enumerate(uf.parents):
    if y < 0:
        x[i] = 0

for l, r, d in graph:
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
        continue
    if l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d


if max(x.values()) - min(x.values()) > 10**9:
    ans = "No"
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):
        return {i for i, x in enumerate(self.parents) if x < 0}


n, m = map(int, input().split())
graph = []
uf = UnionFind(n+1)
for _ in range(m):
    l, r, d = map(int, input().split())
    uf.union(l, r)
    graph.append((l, r, d))

x = {0: 0}
ans = "Yes"
# 根の座標を０で確定
for i, y in enumerate(uf.parents):
    if y < 0:
        x[y] = 0

for l, r, d in graph:
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
        continue
    if l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d


if max(x.values()) - min(x.values()) > 10**9:
    ans = "No"
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
INF=10**18
path=[[INF]*n for i in range(n)]
for i in range(m):
  u,v,c=map(int,input().split())
  path[u-1][v-1]=c
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i==j or j==k or k==i:continue
      if path[i][k]!=INF and path[k][j]!=INF and path[i][j]!=INF:
        if path[i][k]+path[k][j]!=path[i][j]:
          print('No')
          exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=[0]*n
l=[0]*m
r=[0]*m
d=[0]*m
for i in range(m):
  l[i],r[i],d[i]=map(int,input().split())
  x[r[i]-1]=x[l[i]-1]+d[i]
for i in range(m):
  if x[r[i]-1]!=x[l[i]-1]+d[i]:
    print('No')
    exit()
if max(x)-min(x)>10**9:
  print('No')
  exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=[0]*n
l=[0]*m
r=[0]*m
d=[0]*m
for i in range(m):
  l[i],r[i],d[i]=map(int,input().split())
  x[r[i]-1]=x[l[i]-1]+d[i]
for i in range(m):
  if x[r[i]-1]!=x[l[i]-1]+d[i]:
    print('No')
    exit()
print('Yes')