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: Time Limit Exceeded

Solution code:
def main():
	N, M = map(int,input().split())
	INF = 10**9+7
	if M == 0:
		print("Yes")
		return
	x = [[INF for _ in range(N)] for _ in range(N)]
	for i in range(M):
		l, r, d = map(int, input().split())
		l, r = l-1, r-1
		x[l][r] = d
		x[r][l] = -d
	ans_exist = True
	for k in range(N):
		for i in range(N):
			for j in range(N):
				if x[i][j] == INF:
					continue
				x[i][j] = min(x[i][j], x[i][k]+x[k][j])

	for i in range(N):
		for j in range(N):
			if x[i][j] == x[j][i] and x[i][j] == INF:
				continue
			if x[i][j] != -x[j][i]:
				ans_exist = False
				break
	if ans_exist:
		print("Yes")
	else:
		print("No")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append([l-1,d])
        e[l-1].append([r-1,-d])
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):
        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()


    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)


    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append([l-1,d])
        e[l-1].append([r-1,-d])
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):
        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()


    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)


    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
N,M = map(int,input().split())
e = [[] for i in range(N)]
t = 0
a = []
for i in range(M):
    r,l,d = map(int,input().split())
    e[r-1].append([l-1,d])
    e[l-1].append([r-1,-d])
    a.append(r-1)
    a.append(l-1)
    t = r-1

col = [ float("inf") for i in range(N) ]
def dfs(i,c):

    for node in e[i]:
        if col[node[0]] == float("inf"):
            col[node[0]] = c + node[1]
            dfs(node[0],c+node[1])
        elif col[node[0]] != c + node[1]:
            print("No")
            exit()


dfs(t,0)
a = list(set(a))
for i in a:
    if col[i] == float("inf"):
        dfs(i,0)


print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

graph = [{} for _ in range(N)]
for l, r, d in LRD:
	l, r = l - 1, r - 1
	graph[l][r] = d
	graph[r][l] = -d

visited = [False] * N
def dfs(v, p, d, depths):
	if visited[v]:
		return True
	visited[v] = True

	if depths[v] != -1:
		return True
	depths[v] = d

	for n in graph[v]:
		if n == p:
			continue
		n_depth = d + graph[v][n]
		if depths[n] != -1 and depths[n] != n_depth:
			return False
		result = dfs(n, v, n_depth, depths)
		if not result:
			return False
	return True

for n in range(N):
	if not dfs(n, -1, 0, [-1] * N):
		print("No")
		break
else:
	print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5+5)
n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    graph[r-1].append((l-1,-d))
    graph[l-1].append((r-1,d))
INF=10**9
x_list=[INF]*n
def dfs(x):
    for i in graph[x]:
        if x_list[i[0]]==INF:
            x_list[i[0]]=x_list[x]+i[1]
            dfs(i[0])
        else:
            if x_list[i[0]]==x_list[x]+i[1]:
                pass
            else:
                print('No')
                sys.exit()
for i in range(n):
    if x_list[i]==INF:
        x_list[i]=0
        dfs(i)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    graph[r-1].append((l-1,-d))
    graph[l-1].append((r-1,d))
INF=10**10
x_list=[INF]*n
def dfs(x):
    for i in graph[x]:
        if x_list[i[0]]==INF:
            x_list[i[0]]=x_list[x]+i[1]
            dfs(i[0])
        else:
            if x_list[i[0]]==x_list[x]+i[1]:
                pass
            else:
                print('No')
                sys.exit()
for i in range(n):
    if x_list[i]==INF:
        x_list[i]=0
        dfs(i)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(_) for _ in input().split()]
c = []
flag = True
g = [[-1, -1] for _ in range(n)]
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l -= 1
    r -= 1
    if g[l][0] != -1 and g[r][0] != -1 and g[l][0] == g[r][0]:
        if c[g[l][0]][g[r][1]][1] - c[g[l][0]][g[l][1]][1] != d:
            flag = False
            break
    elif g[l][0] != -1 and g[r][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        r_pos = c[g[r][0]][g[r][1]][1]

        for j in c[g[r][0]]:
            j[1] += l_pos + d - r_pos
        c[g[l][0]].extend(c[g[r][0]])
        del c[g[r][0]]
    elif g[l][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        c[g[l][0]].append([r, l_pos+d])
        g[r][0] = g[l][0]
        g[r][1] = len(c[g[l][0]])-1
    elif g[r][0] != -1:
        r_pos = c[g[r][0]][g[r][1]][1]
        c[g[r][0]].append([l, r_pos-d])
        g[l][0] = g[r][0]
        g[l][1] = len(c[g[r][0]])-1
    else:
        c.append([[l, 0], [r, d]])
        g[l][0] = max(g, key=lambda x: x[0])[0]+1
        g[r][0] = g[l][0]
        g[l][1] = 0
        g[r][1] = 1
if flag:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(_) for _ in input().split()]
c = []
flag = True
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l_in = False
    r_in = False
    for j in range(len(c)):
        c_tmp = [_[0] for _ in c[j]]
        if l in c_tmp and r in c_tmp:
            if c[j][c_tmp.index(r)][1] - c[j][c_tmp.index(l)][1] != d:
                flag = False
                break
        elif l in c_tmp:
            l_in = True
            l_group = j
            l_pos = c[j][c_tmp.index(l)][1]
        elif r in c_tmp:
            r_in = True
            r_group = j
            r_pos = c[j][c_tmp.index(r)][1]
    if l_in and r_in:
        for j in range(len(c[r_group])):
            c[r_group][j][1] += l_pos + d - r_pos
        c[l_group].extend(c[r_group])
        del c[r_group]
    elif l_in:
        c[l_group].append([r, l_pos+d])
    elif r_in:
        c[r_group].append([l, r_pos-d])
    else:
        c.append([[l, 0], [r, d]])

    if not flag:
        break

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

Submission status: Time Limit Exceeded

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

def dfs(v):
  if len(g[v])==0:
    dist[v]=v
  else:
    for b,d in g[v]:
      if dist[b]==10**10:
        dist[b]=dist[v]+d
        dfs(b)
      else:
        if dist[b]-dist[v]!=d:
          print('No')
          exit(0)

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
dist=[10**10]*(n+1)
for _ in range(m):
  a,b,d=map(int,input().split())
  g[a].append([b,d])
  g[b].append([a,-d])
flag=False
for i in range(1,n+1):
  if dist[i]==10**10:
    dist[i]=i
  dfs(i)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
L=[[] for i in range(N)]
D=["" for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  L[a-1].append([b-1,c])
  L[b-1].append([a-1,-c])
memo=[]
j=0
s=0
n=0
while not s:  
  
  if not memo:
    if n==N:
      break
    j=D[j:].index("")+j
    D[j]=0
    memo.append(j)
    n+=1
    continue
  k=memo.pop()
  for x,c in L[k]:
    if D[x]=="":
      D[x]=D[k]+c
      memo.append(x)
      n+=1
    elif D[x]!=D[k]+c:
      
      s=1
      break
  
print("No" if s else "Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
L=[[] for i in range(N)]
D=["" for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  L[a-1].append([b-1,c])
  L[b-1].append([a-1,-c])
memo=[]
j=0
s=0
n=0
while True:
  
  if not memo:
    if n==N:
      break
    
    j=D[j:].index("")+j
    D[j]=0
    memo.append(j)
    n+=1
    continue
  k=memo.pop()
  
  for x,c in L[k]:
    
    if D[x]=="":
      D[x]=D[k]+c
      memo.append(x)
      n+=1
    elif D[x]!=D[k]+c:
      s=1
      break
  if s:
    break
print("No" if s else "Yes")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
L=[[] for i in range(N)]
D=["" for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  L[a-1].append([b-1,c])
  L[b-1].append([a-1,-c])
memo=[]
j=0
s=0
n=0
while True:
  
  if not memo:
    if n==N:
      break
    
    j=D[j:].index("")+j
    D[j]=0
    memo.append(j)
    n+=1
    continue
  k=memo.pop()
  
  for x,c in L[k]:
    
    if D[x]=="":
      D[x]=D[k]+c
      memo.append(x)
      n+=1
    elif D[x]!=D[k]+c:
      s=1
      break
  if s:
    break
print("No" if s else "Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int,input().split())
if M==0:
    print("Yes")
    quit()
G=[[] for i in range(N)]
for i in range(M):
    l,r,d=map(int,input().split())
    G[l-1].append((l-1,r-1,d))
    G[r-1].append((r-1,l-1,-d))
x=["a"]*N
y=[1]*N
z=[[0]*N for i in range(N)]
stack=deque()
for i in range(N):
    if y[i]:
        stack.extend(G[i])
        y[i]=0
    if len(stack)==0:
        continue
    while(stack):
        l,r,d=stack.popleft()
        if x[l]=="a":
            x[l]=0
        if x[r]=="a":
            x[r]=x[l]+d
            continue
        if x[r]!=x[l]+d:
            print("No")
            quit()
        y[r]=0
        z[l][r]=1
        z[r][l]=1
        for l1,r1,d1 in G[r]:
            if z[l1][r1] or z[r1][l1]:
                continue
            stack.append((l1,r1,d1))
if max(x)-min(x)>10**9:
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

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

from collections import deque
N,M=map(int,input().split())
if M==0:
    print("Yes")
    quit()
G=[[] for i in range(N)]
for i in range(M):
    l,r,d=map(int,input().split())
    G[l-1].append((l-1,r-1,d))
    G[r-1].append((r-1,l-1,-d))
x=["a"]*N
y=[1]*N
z=[[0]*N for i in range(N)]
stack=deque()
for i in range(N):
    if y[i]:
        stack.extend(G[i])
        y[i]=0
    if len(stack)==0:
        continue
    while(stack):
        l,r,d=stack.popleft()
        if x[l]=="a":
            x[l]=0
        if x[r]=="a":
            x[r]=x[l]+d
            continue
        if x[r]!=x[l]+d:
            print("No")
            quit()
        y[r]=0
        z[l][r]=1
        for l1,r1,d1 in G[r]:
            if z[l1][r1]:
                continue
            stack.append((l1,r1,d1))
if max(x)-min(x)>10**9:
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
d={i:[-float('inf'),{}] for i in range(n)}
for i in range(m):
  l,r,x=map(int,input().split())
  d[l-1][1][r-1]=x
  d[r-1][1][l-1]=-x
f=True
checked=set([i for i in range(n)])
while(checked and f):
  p=checked.pop()
  q=[p]
  d[p][0]=0
  tmp_checked={p}
  while(q and f):
    q_=q.pop(0)
    l=d[q_][0]
    for x in d[q_][1]:
      if x in checked:
        checked.remove(x)
      if d[x][0]==-float('inf'):
        d[x][0]=l+d[q_][1][x]
        if x not in tmp_checked:
          tmp_checked.add(x)
          q.append(x)
      else:
        if d[x][0]!=l+d[q_][1][x]:
          f=False
          break
print('Yes' if f else 'No')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
d={i:[-float('inf'),{}] for i in range(n)}
for i in range(m):
  l,r,x=map(int,input().split())
  d[l-1][1][r-1]=x
  d[r-1][1][l-1]=-x
f=True
checked=set([i for i in range(n)])
while(checked and f):
  p=checked.pop()
  q=[p]
  d[p][0]=0
  while(q and f):
    q_=q.pop(0)
    l=d[q_][0]
    for x in d[q_][1]:
      if x in checked:
        checked.remove(x)
      if d[x][0]==-float('inf'):
        d[x][0]=l+d[q_][1][x]
        q.append(x)
      else:
        if d[x][0]!=l+d[q_][1][x]:
          f=False
          break
print('Yes' if f else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
N, M = map(int,input().split())
if M == 0:
    print("Yes")
    exit(0)

INF = float("inf")
G = [[] for k in range(N)]
D = [INF for k in range(N)]
def dfs(x):
    if len(G[x]) == 0:
        D[x] = x
    else:
        for e in G[x]:
            if D[e[0]] == INF:
                D[e[0]] = D[x] + e[1]
                dfs(e[0])
            else:
                if D[e[0]] != D[x] + e[1]:
                    print("No")
                    exit(0)

for k in range(M):
    L, R, S = map(int,input().split())
    G[L-1].append([R-1,S])
    G[R-1].append([L-1,-S])

for k in range(N):
    if D[k] == INF:
        D[k] = k
        dfs(k)
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100001)
N, M = map(int,input().split())
if M == 0:
    print("Yes")
    exit(0)

INF = float("inf")
G = [[] for k in range(N)]
D = [INF for k in range(N)]
def dfs(x):
    if len(G[x]) == 0:
        D[x] = x
    else:
        for e in G[x]:
            if D[e[0]] == INF:
                D[e[0]] = D[x] + e[1]
                dfs(e[0])
            else:
                if D[e[0]] != D[x] + e[1]:
                    print("No")
                    exit(0)

for k in range(M):
    L, R, S = map(int,input().split())
    G[L-1].append([R-1,S])
    G[R-1].append([L-1,-S])

for k in range(N):
    if D[k] == INF:
        D[k] = k
        dfs(k)
print("Yes")

Submission status: Time Limit Exceeded

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

if M == 0:
    print('Yes')
    exit()

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 = {}

l, r, d = L.pop(), R.pop(), D.pop()
X[l] = 0
X[r] = d

i = 0
while len(D) > 0:
    l, r, d = L[i], R[i], D[i]
    if l in X or r in X:
        if l in X and r in X:
            if X[r] - X[l] != d:
                print('No')
                exit()
        elif l in X:
            X[r] = X[l] + d
        else:
            X[l] = X[r] - d

        del L[i]
        del R[i]
        del D[i]

    i = (i + 1) % max(1, len(D))

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        self.potential=[0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            r = self.Find_Root(self.root[x])
            self.potential[x] += self.potential[self.root[x]]
            self.root[x]=r
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y, d):
        d+=self.potential[x]-self.potential[y]
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.potential[y]=d

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.potential[x]=-d
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def dist(self,x,y):
        if self.isSameGroup(x,y):
            return self.potential[y]-self.potential[x]
        else: return -10**10




INF=10**10
N,M=map(int,input().split())
if M==0: print("Yes"),sys.exit()
tree=UnionFind(N)


dist=[list(map(int,input().split())) for i in range(M)]
for i in range(M):
    l,r,d=dist[i]
    if tree.isSameGroup(l,r) and tree.dist(l,r)!=d: print("No"),sys.exit()
    tree.Unite(l,r,d)

for i in range(M):
    l,r,d=dist[i]
    if tree.dist(l,r)!=d:
        print("No")
        sys.exit()

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        self.potential=[0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            r = self.Find_Root(self.root[x])
            self.potential[x] += self.potential[self.root[x]]
            self.root[x]=r
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y, d):
        d+=self.potential[x]-self.potential[y]
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.potential[y]=d

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.potential[x]=-d
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def dist(self,x,y):
        if self.isSameGroup(x,y):
            return self.potential[y]-self.potential[x]
        else: return -10**10



INF=10**10

N,M=map(int,input().split())
if M==0: print("Yes"),sys.exit()

tree=UnionFind(N)
dist=[list(map(int,input().split())) for i in range(M)]

for i in range(M):
    l,r,d=dist[i]
    if tree.isSameGroup(l,r) and tree.dist(l,r)!=d: print("No"),sys.exit()
    tree.Unite(l,r,d)

for i in range(M):
    l,r,d=dist[i]
    if tree.dist(l,r)!=d:
        print("No")
        sys.exit()

print("Yes")

Submission status: Time Limit Exceeded

Solution code:

import sys

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        self.potential=[0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            r = self.Find_Root(self.root[x])
            self.potential[x] += self.potential[self.root[x]]
            self.root[x]=r
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y, d):
        d+=self.potential[x]-self.potential[y]
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.potential[y]=d

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.potential[x]=-d
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def dist(self,x,y):
        if self.isSameGroup(x,y):
            return self.potential[y]-self.potential[x]
        else: return -10**10



INF=10**10

N,M=map(int,input().split())
if M==0 or N<=2: print("Yes"),sys.exit()

tree=UnionFind(N)
dist=[list(map(int,input().split())) for i in range(M)]

for i in range(M):
    l,r,d=dist[i]
    if tree.isSameGroup(l,r) and tree.dist(l,r)!=d: print("No"),sys.exit()
    tree.Unite(l,r,d)

for i in range(M):
    l,r,d=dist[i]
    if tree.dist(l,r)!=d:
        print("No")
        sys.exit()

print("Yes")

Submission status: Time Limit Exceeded

Solution code:

import sys
from itertools import accumulate as acc
sys.setrecursionlimit(10**6)

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def cur(n):
    tmp=[dic[n][j] for j in range(len(dic[n]))]
    for i in dic[n]:
        x[i]=x[n]+memo[n][i]
        dic[i].remove(n)
        dic[n].remove(i)
        
    for i in tmp:
        cur(i)



INF=10**10
N,M=map(int,input().split())
if M==0: print("Yes"),sys.exit()
dic=[[] for i in range(N+1)]
memo=[[-INF for j in range(N+1)] for i in range(N+1)]
tree=UnionFind(N)


dist=[list(map(int,input().split())) for i in range(M)]
for i in range(M):
    l,r,d=dist[i]
    tree.Unite(l,r)
    memo[l][r]=d
    memo[r][l]=-d
    dic[l].append(r)
    dic[r].append(l)

s=set()
for i in range(1,N+1):
    s.add(tree.Find_Root(i))


x=[-INF]*(N+1)
for i in s:
    x[i]=0
    cur(i)

for i in range(M):
    l,r,d=dist[i]
    if x[r]-x[l]!=d: print("No"),sys.exit()

print("Yes")

Submission status: Time Limit Exceeded

Solution code:

import sys
from itertools import accumulate as acc
sys.setrecursionlimit(10**6)

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def cur(n):
    for i in dic[n]:
        x[i]=x[n]+memo[n][i]
        dic[n].remove(i)
        dic[i].remove(n)
        cur(i)



INF=10**10
N,M=map(int,input().split())
if M==0: print("Yes"),sys.exit()
dic=[[] for i in range(N+1)]
memo=[[-INF for j in range(N+1)] for i in range(N+1)]
tree=UnionFind(N)


dist=[list(map(int,input().split())) for i in range(M)]
for i in range(M):
    l,r,d=dist[i]
    tree.Unite(l,r)
    memo[l][r]=d
    memo[r][l]=-d
    dic[l].append(r)
    dic[r].append(l)

s=set()
for i in range(1,N+1):
    s.add(tree.Find_Root(i))


x=[-INF]*(N+1)
for i in s:
    x[i]=0
    cur(i)

for i in range(M):
    l,r,d=dist[i]
    if x[r]-x[l]!=d: print("No"),sys.exit()

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    cons = [[] for _ in range(N + 1)]
    for j in range(M):
        cons[R[j]].append([L[j], -D[j], False, len(cons[L[j]])])
        cons[L[j]].append([R[j], D[j], False, len(cons[R[j]]) - 1])

    vals = [None] * (N + 1)
    visited = [False] * (N + 1)
    #print(cons)

    def dfs(idx):
        #print(idx)
        #print(visited)
        #print(vals)
        #print()
        #visited[idx] = True
        #for t, d, used in cons[idx]:
        for con in cons[idx]:
            t = con[0]
            d = con[1]
            used = con[2]
            if not used:
                #print(idx, t, d, vals[idx], vals[t])
                if vals[idx] is None:
                    vals[idx] = 0
                if vals[t] is None:
                    vals[t] = vals[idx] + d
                elif vals[t] != vals[idx] + d:
                    return False
                con[2] = True
                cons[t][con[3]][2] = True
                if not visited[t]:
                    dfs(t)
        return True

    ret = YES
    for i in range(1, N + 1):
        if not visited[i]:
            res = dfs(i)
            if not res:
                ret = NO
                break
    #print(cons)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    cons = [[] for _ in range(N + 1)]
    for j in range(M):
        cons[R[j]].append([L[j], -D[j], False])
        cons[L[j]].append([R[j], D[j], False])

    vals = [None] * (N + 1)
    visited = [False] * (N + 1)
    #print(cons)

    def dfs(idx):
        #print(idx)
        #print(visited)
        #print(vals)
        #print()
        #visited[idx] = True
        #for t, d, used in cons[idx]:
        for con in cons[idx]:
            t = con[0]
            d = con[1]
            used = con[2]
            if not used:
                #print(idx, t, d, vals[idx], vals[t])
                if vals[idx] is None:
                    vals[idx] = 0
                if vals[t] is None:
                    vals[t] = vals[idx] + d
                elif vals[t] != vals[idx] + d:
                    return False
                con[2] = True
                if not visited[t]:
                    dfs(t)
        return True

    ret = YES
    for i in range(1, N + 1):
        if not visited[i]:
            res = dfs(i)
            if not res:
                ret = NO
                break
    #print(cons)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()