Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

1 \leq L_i, R_i \leq N (1 \leq i \leq M)

0 \leq D_i \leq 10 000 (1 \leq i \leq M)

L_i \neq R_i (1 \leq i \leq M)

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

D_i are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

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

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

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

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



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


Sample output:
Yes

Submission status: Wrong Answer

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

edges = [[] for _ in range(N+1)]
for _ in range(M):
    L, R, D = list(map(int, input().split()))
    edges[L].append((R, D))
    edges[R].append((L,-D))

x = [-1]*(N+1)
for i in range(1,N+1):
    if x[i]!=-1: continue
    queue = [i]
    x[i] = 0
    minx = maxx = 0
    while len(queue)>0:
        queue_new = []
        for q in queue:
            for r, d in edges[q]:
                dist = x[q] + d
                if x[r]==-1:
                    x[r] = dist
                    queue_new.append(r)
                elif x[r]!=dist:
                    print('No')
                    exit()
                    
        queue = queue_new

print('Yes')

Submission status: Wrong Answer

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

edges = [[] for _ in range(N+1)]
for _ in range(M):
    L, R, D = list(map(int, input().split()))
    edges[L].append((R, D))
    edges[R].append((L,-D))

x = [-1]*(N+1)
for i in range(1,N+1):
    if x[i]!=-1: continue
    queue = [i]
    x[i] = 0
    minx = maxx = 0
    while len(queue)>0:
        queue_new = []
        for q in queue:
            for r, d in edges[q]:
                dist = x[q] + d
                if x[r]==-1:
                    x[r] = dist
                    minx = min(dist, minx)
                    maxx = max(dist, maxx)
                    queue_new.append(r)
                elif x[r]!=dist:
                    print('No')
                    exit()
                    
        queue = queue_new
    if maxx-minx>10**9:
        print('No')
        exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
n, m = [ int(v) for v in input().split() ]
parent_list = [ i for i in range(n) ]
node = []
distance_from_parent = [ 0 for i in range(n) ]

for i in range(m):
    l, r, d = [ int(v) for v in input().split() ]
    node.append((l-1,r-1,d))

def root(x):
    while parent_list[x] != x:
        parent_list[x] = parent_list[parent_list[x]]  
        x = parent_list[x]   
    return x

for i in node:
    l, r, d = i
    rootl, rootr = root(l), root(r)
    if l > r:
        d *= -1
    if rootl != rootr:
        parent_list[rootr] = rootl
        distance_from_parent[r] = distance_from_parent[l] + d

ans = "Yes"
for i in node:
    l, r, d = i
    if l > r:
        d *= -1
    if distance_from_parent[r] != distance_from_parent[l] + d:
        ans = "No"
        break
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [ int(v) for v in input().split() ]
parent_list = [ i for i in range(n) ]
node = []
distance_from_parent = [ 0 for i in range(n) ]

for i in range(m):
    l, r, d = [ int(v) for v in input().split() ]
    node.append((l-1,r-1,d))

def root(x):
    while parent_list[x] != x:
        parent_list[x] = parent_list[parent_list[x]]  
        x = parent_list[x]   
    return x

for i in node:
    l, r, d = i
    rootl, rootr = root(l), root(r)
    if l > r:
        d *= -1
    if rootl != rootr:
        parent_list[rootr] = rootl
        distance_from_parent[r] = distance_from_parent[l] + d

ans = "Yes"
for i in node:
    l, r, d = i
    if distance_from_parent[r] != distance_from_parent[l] + d:
        ans = "No"
        break
print(ans)

Submission status: Wrong Answer

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

G = [{} for _ in range(N+1)]
for L, R, D in LRD:
    G[L][R] = D
    G[R][L] = -D

visited = [False] * (N+1)
dist = [0] * (N+1)


def dfs(v):
    q = [v]
    while q:
        cu = q.pop()
        for nx, d in G[cu].items():
            if visited[nx]:
                if dist[nx] != dist[cu] + D:
                    print('No')
                    exit()
            else:
                visited[nx] = True
                dist[nx] = dist[cu] + D
                q.append(nx)
    return True


for n in range(1, N+1):
    if not visited[n]:
        dfs(n)
print('Yes')

Submission status: Wrong Answer

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

n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    l,r,d=map(int,input().split())
    g[l-1].append([r-1,d])
    g[r-1].append([l-1,d*(-1)])
f=[False for _ in range(n)]

def dfs(s,x):
    f[s] = x
    for sg in g[s]:
        if f[sg[0]] != 0 and (not f[sg[0]]):
            if not dfs(sg[0],sg[1]+x):
                return False
        else:
            if f[sg[0]] - f[s] != sg[1]:
                return False
    return True

def main():
    for i in range(n):
        if f[i] != 0 and (not f[i]):
            if not dfs(i,1):
                return "No"
    return "Yes"

print(main())

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    l,r,d=map(int,input().split())
    g[l-1].append([r-1,d])
    g[r-1].append([l-1,d*(-1)])
INF = 10**10
f=[INF for _ in range(n)]

import sys
sys.setrecursionlimit(10**7)

def dfs(s,x):
    global f,g,INF
    f[s] = x
    for sg in g[s]:
        if f[sg[0]] == INF:
            dfs(sg[0],sg[1]+x)
        else:
            if f[sg[0]] - f[s] != sg[1]:
                return False
    return True

def main():
    for i in range(n):
        if f[i] == INF:
            if not dfs(i,0):
                return "No"

    return "Yes"

print(main())

Submission status: Wrong Answer

Solution code:
#people on line
#unionfind
class UnionFind:
    def __init__(self, n):
        self.par =[i for i in range(n+1)]
        self.rank = [0] * (n+1)
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m=map(int,input().split())
Uni=UnionFind(n)
distance=["N" for i in range(n)]
flag=True
#訪れてない時は”ｎ”、訪れた時はなんらかの数字で表現される
for _ in range(m):
    l,r,d=map(int,input().split())
    Uni.union(l,r)
    Uni.find(l)
    Uni.find(r)
    if distance[l-1]=="N" and distance[r-1]=="N":
        distance[l-1]=0
        distance[r-1]=d
    elif distance[l-1]!="N" and distance[r-1]=="N":
        distance[r-1]=d+distance[l-1]
    elif distance[l-1]=="N" and distance[r-1]!="N":
        distance[l-1]=distance[r-1]-d
    elif distance[l-1]!="N" and distance[r-1]!="N":
        if distance[r-1]-distance[l-1]!=d:
            flag=False
            break
if not flag and m!=0:
    print("No")
elif flag and m!=0:
    A=Uni.par
    del A[0]
    flag2=True
    lists=[[] for i in range(n)]
    #parentがどこに入るかで区別
    for k in range(n):
        if distance[k]!="N":
            lists[A[k]-1].append(distance[k]) 
    for some in lists:
        if some:
            maxi=max(some)
            mini=min(some)
            if maxi-mini>10**9:
                flag2=False
                break
    if flag2:
        print("Yes")
    if not flag2:
        print("No")               
elif m==0:
    print("Yes")

Submission status: Wrong Answer

Solution code:
#people on line
n,m=map(int,input().split())
distance=["N" for i in range(n)]
flag=True
#訪れてない時は”ｎ”、訪れた時はなんらかの数字で表現される
for _ in range(m):
    l,r,d=map(int,input().split())
    if distance[l-1]=="N" and distance[r-1]=="N":
        distance[l-1]=0
        distance[r-1]=d
    elif distance[l-1]!="N" and distance[r-1]=="N":
        distance[r-1]=d+distance[l-1]
    elif distance[l-1]=="N" and distance[r-1]!="N":
        distance[l-1]=distance[r-1]-d
    elif distance[l-1]!="N" and distance[r-1]!="N":
        if distance[r-1]-distance[l-1]!=d:
            flag=False
            break
if flag:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
#people on line
#unionfind
class UnionFind:
    def __init__(self, n):
        self.par =[i for i in range(n+1)]
        self.rank = [0] * (n+1)
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m=map(int,input().split())
Uni=UnionFind(n)
distance=["N" for i in range(n)]
flag=True
#訪れてない時は”ｎ”、訪れた時はなんらかの数字で表現される
for _ in range(m):
    l,r,d=map(int,input().split())
    Uni.union(l,r)
    Uni.find(l)
    Uni.find(r)
    if distance[l-1]=="N" and distance[r-1]=="N":
        distance[l-1]=0
        distance[r-1]=d
    elif distance[l-1]!="N" and distance[r-1]=="N":
        distance[r-1]=d+distance[l-1]
    elif distance[l-1]=="N" and distance[r-1]!="N":
        distance[l-1]=distance[r-1]-d
    elif distance[l-1]!="N" and distance[r-1]!="N":
        if distance[r-1]-distance[l-1]!=d:
            flag=False
            break


if not flag and m!=0:
    print("No")
elif flag and m!=0:
    A=Uni.par
    del A[0]
    flag2=True
    lists=[[] for i in range(n)]
    #parentがどこに入るかで区別
    for k in range(n):
        lists[A[k]].append(distance[k]) 
    for some in lists:
        if some:
            maxi=max(some)
            mini=min(some)
            if maxi-mini>10**9:
                flag2=False
                break
    if flag2:
        print("Yes")
    if not flag2:
        print("No")
                
elif m==0:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	a=[0]*(n+1)
	li=[]
	for i in range(m):
		l,r,d=map(int,input().split())
		a[r]=a[l]+d
		li.append((l,r,d))
	
	for l,r,d in li:
		if a[r]!=a[l]+d:
			print("No")
			exit(0)
	
	print("Yes")
	
	
	
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
adj_x = -1
list_x = [adj_x for _ in range(n)]

for i in range(m):
  l, r, d = map(int, input().split())
  l -= 1
  r -= 1
  if list_x[l] == -1 and list_x[r] == -1:
    if adj_x < 0:
      adj_x = 0
    list_x[l] = adj_x
    list_x[r] = adj_x + d
  elif list_x[l] != -1 and list_x[r] == -1:
    list_x[r] = list_x[l] + d
  elif list_x[l] == -1 and list_x[r] != -1:
    list_x[l] = list_x[r] - d
    if list_x[l] < 0:
      adj_x = abs(list_x[l])
      list_x = [adj_x + one_x if one_x != -1 else -1 for one_x in list_x]
  else:
    if list_x[r] - list_x[l] != d:
      print("No")
      exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n, m = map(int, input().split())
    pos = [-1] * n
    rld = []
    for _ in range(m):
        l, r, d = map(int, input().split())
        l, r = l - 1, r - 1
        rld.append([r, l, d])
    rld.sort()
    for r, l, d in rld:
        if pos[l] == -1: pos[l] = 0
        if pos[r] == -1:
            pos[r] = pos[l] + d
        else:
            if pos[r]!=pos[l]+d:
                print("No")
                exit()
    print("Yes")
main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[[] for i in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li[l].append((r,d))
		#li[r].append((l,-d))
	
	stack=[]
	check=set()
	a=[-10**10]*(n+1)
	
	for i in range(1,n+1):
		if li[i]==[""] or (i in check):
			continue
		else:
			stack.append(i)
			a[i]=0
			while stack:
				now=stack.pop()
				check.add(now)
				for j in li[now]:
					if j[0] in check:
						if a[j[0]]-a[now]!=j[1]:
							print("No")
							exit(0)
						else:
							continue
					if j[0] in stack:
						continue
					a[j[0]] = a[now] + j[1]
					stack.append(j[0])
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[]
	li2=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li.append((l,r,d))
		li.append((r,l,-d))
		li2[l].append((r,d))
		li2[r].append((l,-d))
	
	stack=[]
	check=set()
	a=[-10**10]*(n+1)

	for i in li:
		print(i)
		if i[0] in check:
			continue
		else:
			stack.append(i[0])
			a[i[0]]=0
			while stack:
				now=stack.pop()
				check.add(now)
				for j in li2[now]:
					if j[0] in check:
						if a[j[0]]-a[now]!=j[1]:
							print("No")
							exit(0)
						else:
							continue
					if j[0] in stack:
						continue
					a[j[0]] = a[now] + j[1]
					stack.append(j[0])
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import random
INF = float('inf')
N, M = map(int, input().strip().split())
LRD = [list(map(int, input().strip().split())) for _ in range(M)]

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

dic = defaultdict(lambda: INF)
for i in range(M):
	if dic[LRD[i][0]] == INF and dic[LRD[i][1]] == INF:
		dic[LRD[i][0]] = random.randint(-10000, 10000)
		dic[LRD[i][1]] = dic[LRD[i][0]] + LRD[i][2]
	elif dic[LRD[i][0]] == INF and dic[LRD[i][1]] != INF:
		dic[LRD[i][0]] = dic[LRD[i][1]] - LRD[i][2]
	elif dic[LRD[i][0]] != INF and dic[LRD[i][1]] == INF:
		dic[LRD[i][1]] = dic[LRD[i][0]] + LRD[i][2]
	else:
		if dic[LRD[i][0]] + LRD[i][2] == dic[LRD[i][1]]:
			continue
		else:
			print("No")
			break
else:
	print("Yes")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
INF = float('inf')
N, M = map(int, input().strip().split())
LRD = [list(map(int, input().strip().split())) for _ in range(M)]

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

dic = defaultdict(lambda: INF)
for i in range(M):
	if dic[LRD[i][0]] == INF and dic[LRD[i][1]] == INF:
		dic[LRD[i][0]] = 0
		dic[LRD[i][1]] = LRD[i][2]
	elif dic[LRD[i][0]] == INF and dic[LRD[i][1]] != INF:
		dic[LRD[i][0]] = dic[LRD[i][1]] - LRD[i][2]
	elif dic[LRD[i][0]] != INF and dic[LRD[i][1]] == INF:
		dic[LRD[i][1]] = dic[LRD[i][0]] + LRD[i][2]
	else:
		if dic[LRD[i][0]] + LRD[i][2] == dic[LRD[i][1]]:
			continue
		else:
			print("No")
			break
else:
	print("Yes")

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
L = [0]*M
R = [0]*M
D = [0]*M
for i in range(M):
    L[i], R[i], D[i] = map(int, input().split())
    
G = [[] for _ in range(N)]
for i in range(M):
    G[L[i]-1].append([R[i]-1, D[i]])
    G[R[i]-1].append([L[i]-1, -D[i]])
    
ans = "Yes"
visited = [0]*N
for i in range(N):
    if visited[i] == 0:
        ini = i
        q = [[ini, 0]]
        visited[ini] = 1
        while len(q) > 0:
            temp = q.pop(-1)
            pos = temp[0]
            d = temp[1]
            for j in range(len(G[pos])):
                if ini == G[pos][j][0]:
                    if d+G[pos][j][1] != 0:
                        ans = "No"
                        break
                elif visited[G[pos][j][0]] < 2:
                    q.append([G[pos][j][0], d+G[pos][j][1]])
                    visited[G[pos][j][0]] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    g[l - 1].append((r - 1, d))
    g[r - 1].append((l - 1, -d))
l = [None] * n
for i in range(n):
    if l[i] != -1:
        continue
    l[i] = 0
    stack = [i]
    while stack:
        d = stack.pop()
        for node, cost in g[d]:
            if l[node] == None:
                l[node] = l[d] + cost
                stack.append(node)
            else:
                if l[node] != l[d] + cost:
                    print('No')
                    exit(0)
print('Yes')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    g[l - 1].append((r - 1, d))
    g[r - 1].append((l - 1, -d))
l = [-1] * n
for i in range(n):
    if l[i] != -1:
        continue
    l[i] = 0
    stack = [i]
    while stack:
        d = stack.pop()
        for node, cost in g[d]:
            if l[node] == -1:
                l[node] = l[d] + cost
                stack.append(node)
            else:
                if l[node] != l[d] + cost:
                    print('No')
                    exit(0)
print('Yes')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
if m == 0:
    print('Yes')
    exit(0)
g = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    g[l - 1].append((r - 1, d))
    g[r - 1].append((l - 1, -d))
l = [None] * n
l[r - 1] = 0
stack = [r - 1]
while stack:
    d = stack.pop()
    for node, cost in g[d]:
        if l[node] == None:
            l[node] = l[d] + cost
            stack.append(node)
        else:
            if l[node] != l[d] + cost:
                print('No')
                exit(0)
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys;sys.setrecursionlimit(10**9)
class Union_Find():#UnionFind f-根探し u-連結 s-連結? c-要素数
	def __init__(self,n):self.n,self.r=[-1]*n,[0]*n
	def Find_Root(self,x):
		if self.n[x]<0:return x
		else:self.n[x]=self.Find_Root(self.n[x]);return self.n[x]
	def Unite(self,x,y):
		x,y=self.Find_Root(x),self.Find_Root(y)
		if x==y:return
		elif self.r[x]>self.r[y]:self.n[x]+=self.n[y];self.n[y]=x
		else:self.n[y]+=self.n[x];self.n[x]=y;self.r[y]+=self.r[x]==self.r[y]
	def isRootSame(self,x,y):return self.Find_Root(x)==self.Find_Root(y)

n,m=map(int,input().split())
a=[[]for _ in range(n)]
u=Union_Find(n)
for i in range(m):
	l,r,d=map(int,input().split());l-=1;r-=1
	a[l].append((l,r,d))
	a[r].append((r,l,-d))
	u.Unite(l,r)
for i in range(1,n):
	if not u.isRootSame(0,i):
		a[0].append((0,i,0))
		a[i].append((i,0,0))
inf=float("inf")
x=[inf]*n;x[0]=0
q=a[0]
while q:
	p=[]
	for i,j,k in q:
		if x[j]==inf:
			x[j]=x[i]+k
			p+=a[j]
		elif x[i]+k!=x[j]:print("No");exit()
	q=p
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys;sys.setrecursionlimit(10**9)
class Union_Find():#UnionFind f-根探し u-連結 s-連結? c-要素数
  def __init__(self,n):self.n,self.r=[-1]*n,[0]*n
  def Find_Root(self,x):
    if self.n[x]<0:return x
    else:self.n[x]=self.Find_Root(self.n[x]);return self.n[x]
  def Unite(self,x,y):
    x,y=self.Find_Root(x),self.Find_Root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:self.n[x]+=self.n[y];self.n[y]=x
    else:self.n[y]+=self.n[x];self.n[x]=y;self.r[y]+=self.r[x]==self.r[y]
n,m=map(int,input().split())
a=[[]for _ in range(n)]
u=Union_Find(n)
for i in range(m):
	l,r,d=map(int,input().split())
	l-=1; r-=1
	a[l].append((r,d))
	a[r].append((l,-d))
	u.Unite(l,r)
x=[-1]*n
for i in range(n):
	if u.Find_Root(i)==i:x[i]=0
	for l,d in a[i]:
		if x[l]<0:x[l]=x[i]+d
		elif x[i]+d!=x[l]:print("No");exit()
print("Yes")

Submission status: Wrong Answer

Solution code:

def inputs():
    return [int(x) for x in input().split()]
"""
N,M = inputs()
D = [-1]*(N+1)
for i in range(M):
    L,R,d = inputs()
    if i==0:
        D[L]=0
        D[R]=d
    else:
        if D[L]!=-1 and D[R]!=-1:
            D[R] = D[l]+d
        elif D[L]!=-1 and D[R]!=D[L]+d:
            print("No")
            exit()
        elif D[L]==-1 and D[R]!=-1:
            D[L] = D[R]-d
        elif D[L]==-1 and D[R]==-1:
            D[L]
"""
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 size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M = [int(x) for x in input().split()]
uf = UnionFind(N+1)
E = []
for i in range(M):
    L,R,d = inputs()
    E.append((L,R,d))
E= sorted(E,key=lambda x :x[1])
N = [0]*(N+1)
memo = [0]*(len(N))
for i in range(M):
    l = E[i][0]
    r = E[i][1]
    d = E[i][2]
    if memo[r]==0:
        N[r] = N[l]+d
    elif memo[r]!=0:
        if memo[l]==0:
            N[l]=N[r]-d
        else:
            if N[l]!=N[r]-d:
                print("No")
                exit()
    #elif N[r]!=N[l]+d:
    #    print("No")
    #    exit()
    memo[l]=1
    memo[r]=1
print("Yes")

Submission status: Wrong Answer

Solution code:

def inputs():
    return [int(x) for x in input().split()]
"""
N,M = inputs()
D = [-1]*(N+1)
for i in range(M):
    L,R,d = inputs()
    if i==0:
        D[L]=0
        D[R]=d
    else:
        if D[L]!=-1 and D[R]!=-1:
            D[R] = D[l]+d
        elif D[L]!=-1 and D[R]!=D[L]+d:
            print("No")
            exit()
        elif D[L]==-1 and D[R]!=-1:
            D[L] = D[R]-d
        elif D[L]==-1 and D[R]==-1:
            D[L]
"""
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 size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M = [int(x) for x in input().split()]
uf = UnionFind(N+1)
E = []
for i in range(M):
    L,R,d = inputs()
    E.append((L,R,d))
E= sorted(E,key=lambda x :x[0])
N = [0]*(N+1)
memo = [0]*(len(N))
for i in range(M):
    l = E[i][0]
    r = E[i][1]
    d = E[i][2]
    if memo[r]==0:
        N[r] = N[l]+d
    elif memo[r]!=0:
        if memo[l]==0:
            N[l]=N[r]-d
        else:
            if N[l]!=N[r]-d:
                print("No")
                exit()
    
    #elif N[r]!=N[l]+d:
    #    print("No")
    #    exit()
    memo[l]=1
    memo[r]=1
print("Yes")

Submission status: Wrong Answer

Solution code:

def inputs():
    return [int(x) for x in input().split()]
"""
N,M = inputs()
D = [-1]*(N+1)
for i in range(M):
    L,R,d = inputs()
    if i==0:
        D[L]=0
        D[R]=d
    else:
        if D[L]!=-1 and D[R]!=-1:
            D[R] = D[l]+d
        elif D[L]!=-1 and D[R]!=D[L]+d:
            print("No")
            exit()
        elif D[L]==-1 and D[R]!=-1:
            D[L] = D[R]-d
        elif D[L]==-1 and D[R]==-1:
            D[L]
"""
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 size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M = [int(x) for x in input().split()]
uf = UnionFind(N+1)
E = []
for i in range(M):
    L,R,d = inputs()
    E.append((L,R,d))
E= sorted(E,key=lambda x :x[0])
N = [0]*(N+1)
memo = [0]*(len(N))
for i in range(M):
    l = E[i][0]
    r = E[i][1]
    d = E[i][2]
    if N[r]==0 and memo[r]==0:
        N[r] = N[l]+d
    elif N[r]==0 and memo[r]!=0:
        if memo[l]==0:
            N[l]=N[r]-d
        else:
            if N[l]!=N[r]-d:
                print("No")
                exit()
    elif N[r]!=N[l]+d:
        print("No")
        exit()
    memo[l]=1
    memo[r]=1
print("Yes")

Submission status: Wrong Answer

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

e = [[] for _ in range(N+1)]
for l, r, d in LRD:
    if l > r:
        l, r = r, l
        d *= -1
    e[l-1].append((r-1, d))
# print(e)

dp = [-1]*N
dp[0] = 0
for l, e_i in enumerate(e):
    for r, d in e_i:
        # print((l, r), d)
        if dp[r] in [-1, dp[l]+d]:
            dp[r] = dp[l]+d
        else:
            print("No")
            exit()

# print(dp)
print("Yes")

Submission status: Wrong Answer

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

e = [[] for _ in range(N+1)]
for l, r, d in LRD:
    if l > r:
        l, r = r, l
        d *= -1
    e[r].append((l, d))
# print(e)

g = [0]*(N+1)
for r, e_i in enumerate(e):
    s = set(g[l]+d for l, d in e_i)
    # print(s, e_i)
    if len(s) == 0:
        continue
    if len(s) == 1:
        p = s.pop()
        g[r] = p
    else:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Q = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
  a, b, d = Q[i][0], Q[i][1], Q[i][2]
  if a > b: Q[i] = [b, a, -d]
Q.sort()
p = [-1 for _ in range(N + 1)]
for i in range(M):
  a, b, d = Q[i][0], Q[i][1], Q[i][2]
  if p[b] == -1:
    p[b] = p[a] + d
  elif p[a] == -1:
    p[a] = p[b] - d
  else:
    if p[b] - p[a] != d:
      print("No")
      exit(0)
print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Q = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
  a, b, d = Q[i][0], Q[i][1], Q[i][2]
  if a > b: Q[i] = [b, a, -d]
Q.sort()
p = [-1 for _ in range(N + 1)]
for i in range(M):
  a, b, d = Q[i][0], Q[i][1], Q[i][2]
  if p[b] == -1:
    p[b] = p[a] + d
  elif p[a] == -1:
    p[a] = p[b] - d
  else:
    if abs(p[b] - p[a]) != d:
      print("No")
      exit(0)
print("Yes")
#print(p, Q)