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:
from collections import deque

n,m = map(int,input().split())
e = [[] for i in range(n)]

for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append([b,c])
    e[b].append([a,-c])

print(e)
dis = [False]*n

def search(x):

    q = deque([])
    dis[x] = 0
    q.append(x)
    while q:
        now = q.pop()
        for nex,d in e[now]:
            if dis[nex] == False:
                dis[nex] = dis[now]+d
                q.append(nex)
            else:
                if dis[nex] != dis[now]+d:
                    print("No")
                    exit()
        
for i in range(n):
    if e[i] and dis[i] == False:
        search(i)
print("Yes")

Submission status: Wrong Answer

Solution code:
class WeightedUnionFindTree:
    """Disjoint-Set Data Structure with weight

    complexity:
        - init: O(n)
        - find, unite, same: O(alpha(n))
    """

    def __init__(self, n_nodes):
        self.par = [i for i in range(n_nodes)]  # parent
        self.rank = [0] * n_nodes  # depth of tree
        self.weights = [0] * n_nodes

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

    def unite(self, x, y, weight=0):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
            self.weights[root_x] = weight - self.weights[x] + self.weights[y]
        else:
            self.par[root_y] = root_x
            self.weights[root_y] = -weight - self.weights[y] + self.weights[x]
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1

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

    def diff(self, x, y):
        return self.weights[x] - self.weights[y]
import sys
n,m=map(int,input().split())
lrd=[]
tree = WeightedUnionFindTree(n)
for _ in range(m):
    lrd.append(list(map(int,input().split())))
for l,r,d in lrd:
    tree.unite(r-1,l-1,d)
for l,r,d in lrd:
    if tree.diff(r-1,l-1) != d:
        print("No")
        sys.exit()
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
class WeightedUnionFindTree:
    """Disjoint-Set Data Structure with weight

    complexity:
        - init: O(n)
        - find, unite, same: O(alpha(n))
    """

    def __init__(self, n_nodes):
        self.par = [i for i in range(n_nodes)]  # parent
        self.rank = [0] * n_nodes  # depth of tree
        self.weights = [0] * n_nodes

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

    def unite(self, x, y, weight=0):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
            self.weights[root_x] = weight - self.weights[x] + self.weights[y]
        else:
            self.par[root_y] = root_x
            self.weights[root_y] = -weight - self.weights[y] + self.weights[x]
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
        return True
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

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

import sys
n,m=map(int,input().split())
lrd=[]
tree = WeightedUnionFindTree(n)
for _ in range(m):
    lrd.append(list(map(int,input().split())))
for l,r,d in lrd:
    res =tree.unite(l-1,r-1,d)
    if not res:
        print("No")
        sys.exit()
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int,input().split())
parent= [i for i in range(N)]
depth = [0 for i in range(N)]
distance = [0 for i in range(N)]

def find(i):
    if i == parent[i]:
        return i, 0
    p, d = find(parent[i])
    depth[i] = d + 1
    return p, d + 1

def change_distance(i, d):
    while i != parent[i]:
        distance[i] += d
        i = parent[i]

def merge(i, j, d):
    r_i, d_i = find(i)
    r_j, d_j = find(j)
    if r_i == r_j:
        return distance[j] - distance[i] == d
    if d_i < d_j:
        parent[r_i] = r_j
        _, _ = find(i)
        td = distance[j] - d - distance[i]
        change_distance(i, td)
    else:
        parent[r_j] = r_i
        _, _ = find(j)
        td = distance[i] + d - distance[j]
        change_distance(j, td)
    return True

for _ in range(M):
    L, R, D = map(int,input().split())
    if not merge(L-1, R-1, D):
        print('No')
        sys.exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M = LI()
g = [[i,0] for i in range(N+1)]
g_num = [1 for i in range(N+1)]

def find(x,z):
    if g[x][0] == x: return x,z
    r,d = find(g[x][0],g[x][1])
    g[x] = [r,d]
    return g[x][0],g[x][1]+z

def union(x,y,d):
#    if g_num[g[x][0]] < g_num[g[y][0]]:
#        x,y = y,x; d = -d
    g_num[g[x][0]] += g_num[g[y][0]]
    g_num[g[y][0]] = 0
    g[g[y][0]][1] = g[x][1] + d
    g[g[y][0]][0] = g[g[x][0]][0]


for _ in range(M):
    l,r,d = LI()

    if find(l,0)[0] == find(r,0)[0]:
        if g[l][1] + d != g[r][1]:
            print('No')
            exit(0)
    else:
        union(l,r,d)
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M = LI()
g = [[i,0] for i in range(N+1)]
g_num = [1 for i in range(N+1)]

def find(x,z):
    if g[x][0] == x: return x,z
    r,d = find(g[x][0],g[x][1])
    g[x] = [r,d]
    return g[x][0],g[x][1]+z

def union(x,y,d):
    if g_num[g[x][0]] < g_num[g[y][0]]:
        x,y = y,x; d = -d
    g_num[g[x][0]] += g_num[g[y][0]]
    g_num[g[y][0]] = 0
    g[g[y][0]][1] = g[x][1] + d
    g[g[y][0]][0] = g[g[x][0]][0]


for _ in range(M):
    l,r,d = LI()

    if find(l,0)[0] == find(r,0)[0]:
        if g[l][1] + d != g[r][1]:
            print('No')
            exit(0)
    else:
        union(l,r,d)
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M = LI()
g = [[i,0] for i in range(N+1)]
g_num = [1 for i in range(N+1)]

def find(x,z):
    if g[x][0] == x: return x,z
    r,d = find(*g[x])
    g[x] = [r,d]
    return g[x][0],g[x][1]+z

def union(x,y,d):
    if g_num[g[x][0]] < g_num[g[y][0]]:
        x,y = y,x; d = -d
    g_num[g[x][0]] += g_num[g[y][0]]
    g_num[g[y][0]] = 0
    g[g[y][0]][1] = g[x][1] + d
    g[g[y][0]][0] = g[g[x][0]][0]


for _ in range(M):
    l,r,d = LI()

    if find(l,0)[0] == find(r,0)[0]:
        if g[l][1] + d != g[r][1]:
            print('No')
            exit(0)
    else:
        union(l,r,d)
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M = LI()
g = [[i,0] for i in range(N+1)]
g_num = [1 for i in range(N+1)]

def find(x,z):
    if g[x][0] == x: return x,0
    r,d = find(*g[x])
    g[x] = [r,z+d]
    return g[x][0],g[x][1]

def union(x,y,d):
    if g_num[g[x][0]] < g_num[g[y][0]]:
        x,y = y,x; d = -d
    g_num[g[x][0]] += g_num[g[y][0]]
    g_num[g[y][0]] = 0
    g[g[y][0]][1] = g[x][1] + d
    g[g[y][0]][0] = g[g[x][0]][0]


for _ in range(M):
    l,r,d = LI()

    if find(l,g[l][1])[0] == find(r,g[r][1])[0]:
        if g[l][1] + d != g[r][1]:
            print('No')
            exit(0)
    else:
        union(l,r,d)
print('Yes')

Submission status: Wrong Answer

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != -1:
    continue
  dist[i] = 0
  q = deque()
  q.append(i)
  while q:
    v = q.popleft()
    for child in E[v]:
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append(child[0])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != -1:
    continue
  dist[i] = 0
  q = deque()
  q.append(i)
  while q:
    v = q.pop()
    for child in E[v]:
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append(child[0])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
dist = [-1] * N
for i in range(N):
  if dist[i] != -1:
    continue
  dist[i] = 0
  q = deque()
  q.append(i)
  while q:
    v = q.pop()
    for child in E[v]:
      if dist[child[0]] == -1:
        dist[child[0]] = dist[v] + child[1]
        q.append(child[0])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
dist = [-1] * N
for i in range(N):
  if dist[i] != -1:
    continue
  dist[i] = 0
  q = deque()
  q.append([i,-1])
  while q:
    v,parent = q.pop()
    for child in E[v]:
      if child[0] == parent:
        continue
      if dist[child[0]] == -1:
        dist[child[0]] = dist[v] + child[1]
        q.append([child[0],v])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
dist = [-1] * N
for i in range(N):
  if dist[i] != -1:
    continue
  q = deque()
  q.append([i,-1,0])
  while q:
    v,parent,d = q.pop()
#    print("v",v,"dist[v]",dist[v],"d",d)
    if dist[v] == -1:
      # 初めてくる場所
      dist[v] = d
    else:
      # 初めてではない場合
      if dist[v] != d:
        print("No")
        exit(0)
      else:
        continue
    for child in E[v]:
      if child == parent:
        continue
      q.append([child[0],v,d + child[1]])
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
# 入力をL,Rでソートする
# 初めて出てきた数の座標は0として、その相対位置をリストに格納
# 格納済みの数値と異なる数が出てきたらNG

N,M = map(int,input().split())
INF = 10 ** 10
from collections import defaultdict
pos = defaultdict(int)

dist = [None] * M
for i in range(M):
  dist[i] = list(map(int,input().split()))
  if dist[i][0] > dist[i][1]:
    dist[i] = [dist[i][1],dist[i][0],-dist[i][2]]
  
dist = sorted(dist,key = lambda x:(x[0],x[1]))

for i in range(len(dist)):
  L,R,D = dist[i]
  L,R = L-1,R-1
  if L in pos and R in pos:
    if pos[L] + D != pos[R]:
      print("No")
      break
  elif L in pos and R not in pos:
    pos[R] = pos[L] + D
  elif L not in pos and R in pos:
    pos[L] = pos[R] - D
  else:
    pos[L] = 0
    pos[R] = D
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
# 入力をL,Rでソートする
# 初めて出てきた数の座標は0として、その相対位置をリストに格納
# 格納済みの数値と異なる数が出てきたらNG

N,M = map(int,input().split())
INF = 10 ** 10
from collections import defaultdict
pos = defaultdict(int)

dist = [None] * M
for i in range(M):
  dist[i] = list(map(int,input().split()))
  
dist = sorted(dist,key = lambda x:(x[0],x[1]))

for i in range(len(dist)):
  L,R,D = dist[i]
  L,R = L-1,R-1
  if L in pos and R in pos:
    if pos[L] + D != pos[R]:
      print("No")
      break
  elif L in pos and R not in pos:
    pos[R] = pos[L] + D
  elif L not in pos and R in pos:
    pos[L] = pos[R] - D
  else:
    pos[L] = 0
    pos[R] = D
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
  
#print("E",E)
import heapq
dist = [-1] * N
for i in range(N):
#  print("i",i,"dist",dist)
  if dist[i] != -1:
    continue
#  print(i,"から出発")
  q = []
  heapq.heapify(q)
  heapq.heappush(q,(i,-1,0))
  while q:
    v,parent,d = heapq.heappop(q)
#    print("v",v,"dist[v]",dist[v],"d",d)
    if dist[v] == -1:
      # 初めてくる場所
      dist[v] = d
    else:
      # 初めてではない場合
      if dist[v] != d:
        print("No")
        exit(0)
#      print("v",v,"dist[v]",dist[v],d,"と一致したので探索終了")
      continue
    for child in E[v]:
      if child == parent:
        continue
#      print("E[v]",E[v],"append",child[0],v,d + child[1])
      heapq.heappush(q,[child[0],v,d + child[1]])
#  else:
#    print("ループ終了")
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
dist = [-1] * N
for i in range(N):
  if dist[i] != -1:
    continue
  q = deque()
  q.append([i,-1,0])
  while q:
    v,parent,d = q.popleft()
#    print("v",v,"dist[v]",dist[v],"d",d)
    if dist[v] == -1:
      # 初めてくる場所
      dist[v] = d
    else:
      # 初めてではない場合
      if dist[v] != d:
        print("No")
        exit(0)
      else:
        continue
    for child in E[v]:
      if child == parent:
        continue
      q.append([child[0],v,d + child[1]])
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [set() for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].add((R-1,D))
  E[R-1].add((L-1,-D))


# 頂点、親、距離
dist = [-1] * N
for i in range(N):
  if dist[i] != -1:
    continue
  q = []
  q.append([i,-1,0])
  while q:
    v,parent,d = q.pop()
#    print("v",v,"dist[v]",dist[v],"d",d)
    if dist[v] == -1:
      # 初めてくる場所
      dist[v] = d
    else:
      # 初めてではない場合
      if dist[v] != d:
        print("No")
        exit(0)
      else:
        continue
    for child in E[v]:
      if child == parent:
        continue
      q.append([child[0],v,d + child[1]])
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=10**10
MOD=10**9+7
input=sys.stdin.readline

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

#初期値が0の辞書
#from collections import defaultdict
#lrd = defaultdict(lambda: []) 

lrd=[[]]*n

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x)
    for llrrdd in lrd[x]:
        #print(lrd,item,x)
        item=llrrdd[0]
        if answer[item]==-10**10:
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

for i in range(n):
    if checked[i]==0:
        answer = [-10**10]*n
        answer[i]=1
        BFD(i)

print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')
MOD=10**9+7
input=sys.stdin.readline

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

#初期値が0の辞書
from collections import defaultdict
lrd = defaultdict(lambda: []) 

lr=defaultdict(lambda: 0) 

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append(r-1)
    lrd[r-1].append(l-1)
    lr[(l-1,r-1)]=d



def BFD(x):
    global checked,answer
    checked[x]=1
    #print("x>>>",x)
    for item in lrd[x]:
        #print(lrd,item,x)
        ll=min(item,x)
        rr=max(item,x)
        if answer[item]==-1:
            if item<=x:
                answer[item]=answer[x]-lr[(item,x)]
            else:
                answer[item]=answer[x]+lr[(x,item)]
        else:
            if answer[rr]!=answer[ll]+lr[(ll,rr)]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

for i in range(n):
    if checked[i]==0:
        answer = defaultdict(lambda: -10**9) 
        answer[i]=1
        BFD(i)

print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')
MOD=10**9+7
input=sys.stdin.readline

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

#初期値が0の辞書
from collections import defaultdict
lrd = defaultdict(lambda: []) 

lr=defaultdict(lambda: 0) 

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append(r-1)
    lrd[r-1].append(l-1)
    lr[(l-1,r-1)]=d



def BFD(x):
    global checked,answer
    checked[x]=1
    #print("x>>>",x)
    for item in lrd[x]:
        #print(lrd,item,x)
        ll=min(item,x)
        rr=max(item,x)
        if answer[item]==-1:
            if item<=x:
                answer[item]=answer[x]-lr[(item,x)]
            else:
                answer[item]=answer[x]+lr[(x,item)]
        else:
            if answer[rr]!=answer[ll]+lr[(ll,rr)]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

for i in range(n):
    if checked[i]==0:
        answer = defaultdict(lambda: -1) 
        answer[i]=10**8
        BFD(i)

print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')
MOD=10**9+7
input=sys.stdin.readline

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

#初期値が0の辞書
from collections import defaultdict
lrd = defaultdict(lambda: []) 

lr=defaultdict(lambda: 0) 

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append(r-1)
    lrd[r-1].append(l-1)
    lr[(l-1,r-1)]=d



def BFD(x):
    global checked,answer
    checked[x]=1
    #print("x>>>",x)
    for item in lrd[x]:
        #print(lrd,item,x)
        ll=min(item,x)
        rr=max(item,x)
        if answer[item]==-1:
            if item<=x:
                answer[item]=answer[x]-lr[(item,x)]
            else:
                answer[item]=answer[x]+lr[(x,item)]
        else:
            if answer[rr]!=answer[ll]+lr[(ll,rr)]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

for i in range(n):
    if checked[i]==0:
        answer = defaultdict(lambda: -1) 
        answer[i]=1
        BFD(i)

print("Yes")

Submission status: Wrong Answer

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    
    #if M == 0:
    if True:
        TF = 'Yes'
    else:
        L_R_D_arr = []
        for i in range(M):
            _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
            L_R_D_arr.append(_)
        # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
        L_R_D_arr.sort()
        iter_ = [float('inf')]*(N+1)

        TF = 'No'
        iter_[L_R_D_arr[0][0]] = 0
        for L, R, D in L_R_D_arr:
            print(L,R,D)
            if iter_[R] not in [float('inf'),iter_[L]+D]:
                break
            else:
                iter_[R] = iter_[L]+D
        else:
            TF = 'Yes'
        # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)

Submission status: Wrong Answer

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    
    if M == 0:
        TF = 'Yes'
    else:
        L_R_D_arr = []
        for i in range(M):
            _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
            if _[0] < _[1]:
                L_R_D_arr.append(_)
            else:
                L_R_D_arr.append([_[1],_[0],-_[2]])
        # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
        L_R_D_arr.sort()
        iter_ = [float('inf')]*(N+1)

        TF = 'No'
        iter_[L_R_D_arr[0][0]] = 0
        for L, R, D in L_R_D_arr:
            if iter_[R] not in [float('inf'),iter_[L]+D]:
                break
            else:
                iter_[R] = iter_[L]+D
        else:
            TF = 'Yes'
        # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)

Submission status: Wrong Answer

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    
    if M == 0:
        TF = 'Yes'
    else:
        L_R_D_arr = []
        for i in range(M):
            _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
            L_R_D_arr.append(_)
        # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
        L_R_D_arr.sort()
        iter_ = [float('inf')]*(N+1)

        TF = 'No'
        iter_[L_R_D_arr[0][0]] = 0
        for L, R, D in L_R_D_arr:
            if iter_[R] not in [float('inf'),iter_[L]+D]:
                break
            else:
                iter_[R] = iter_[L]+D
        else:
            TF = 'Yes'
        # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
INFTY = 10**10
A = sorted([list(map(int,input().split())) for _ in range(M)],key=lambda x:x[0])
hist = [0 for _ in range(N+1)]
dist = [-INFTY for _ in range(N+1)]
if M>0:
    hist[A[0][0]]=1
    dist[A[0][0]] = 0
    hist[A[0][1]]=1
    dist[A[0][1]] = dist[A[0][0]]+A[0][2]
flag = 0
for i in range(1,M):
#     import ipdb;ipdb.set_trace()
    ind = A[i][0]
    ind2 = A[i][1]
    if hist[ind]==1:
        if hist[ind2]==1:
            if dist[ind2]==dist[ind]+A[i][2]:
                continue
            else:
                flag = 1
                break
        else:
            dist[ind2] = dist[ind]+A[i][2]
            hist[ind2] = 1
    else:
        if hist[ind2]==1:
            dist[ind] = dist[ind2]-A[i][2]
            hist[ind]=1
        else:
            dist[ind] = 0
            hist[ind] = 1
            dist[ind2] = A[i][2]
            hist[ind2]=1
if flag==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().split()]
LRD = [[int(x) for x in input().split()] for _ in range(M)]

LRD.sort()

D = [0] * (N + 1)

for l, r, d in LRD:
    if D[r] == 0:
        D[r] = D[l] + d
    else:
        if D[r] - D[l] != d:
            print("No")
            exit()

for l, r, d in LRD:
    if D[r] - D[l] != d:
        print("No")
        break
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().split()]
LRD = [[int(x) for x in input().split()] for _ in range(M)]

LRD.sort()

D = [0] * (N + 1)

for l, r, d in LRD:
    D[r] = D[l] + d

for l, r, d in LRD:
    if D[r] - D[l] != d:
        print("No")
        break
else:
    print("Yes")

Submission status: Wrong Answer

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

LRD = [tuple(map(int, input().split())) for _ in range(M)]

LRD.sort(key = lambda x: x[0])

MIN = -10 ** 18

lst = [MIN] * (N + 1)

for l, r, d in LRD:
    if lst[l] == MIN:
        if lst[r] == MIN:
            lst[l] = 0
            lst[r] = d
        else:
            lst[l] = lst[r] - d
    else:
        if lst[r] == MIN:
            lst[r] = lst[l] + d
        else:
            if lst[r] != lst[l] + d:
                print ('No')
                exit()

print ('Yes')

# print (lst)

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]


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    uf = WeightedUnionFind(N)
    LRD = [[int(i) for i in input().split()] for j in range(M)]
    for le, ri, d in LRD:
        if uf.same(le, ri):
            # print(le, ri, d, uf.diff(le, ri), uf.diff(ri, le))
            if le < ri:
                if uf.diff(le, ri) != d:
                    return print("No")
            else:
                if uf.diff(ri, le) != d:
                    return print("No")
        if le < ri:
            uf.union(le, ri, d)
        else:
            uf.union(ri, le, -d)
    print("Yes")


if __name__ == '__main__':
    main()

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]


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    uf = WeightedUnionFind(N)
    LRD = [[int(i) for i in input().split()] for j in range(M)]
    for le, ri, d in LRD:
        if uf.same(le, ri):
            # print(le, ri, d, uf.diff(le, ri), uf.diff(ri, le))
            if uf.diff(le, ri) != d:
                return print("No")
        if le < ri:
            uf.union(le, ri, d)
        else:
            uf.union(le, ri, -d)
    print("Yes")


if __name__ == '__main__':
    main()