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:
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:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            self.potential[x] += self.potential[self.root[x]]
            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

n,m=map(int,input().split())
if m==0:
  print('Yes')
else:
  t=UnionFind(n)
  arr=[list(map(int,input().split())) for _ in range(m)]
  for l,r,d in arr:
    if t.isSameGroup(l,r) and t.Dist(l,r)!=d:
      print('No')
      break
    t.Unite(l,r,d)
  else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
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:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            self.potential[x] += self.potential[self.root[x]]
            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

n,m=map(int,input().split())
if m==0:
  print('Yes')
else:
  t=UnionFind(n)
  arr=[list(map(int,input().split())) for _ in range(m)]
  for l,r,d in arr:
    if t.isSameGroup(l,r) and t.Dist(l,r)!=d:
      print('No')
      break
    t.Unite(l,r,d)
  else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[0]*(n+1)
mem=[0]*(n+1)
job=[]
for _ in range(m):
  a,b,d=map(int,input().split())
  if a<=b:
    job.append([a,b,d])
  else:
    job.append([b,a,-d])
job=sorted(job,key=lambda x:x[1])
job=sorted(job,key=lambda x:x[0])
flag=True
for i in range(m):
  a=job[i][0]
  b=job[i][1]
  d=job[i][2]
  tmp=arr[b]-arr[a]
  if mem[a]*mem[b]==0:
  	if mem[b]==0:
  		arr[b]=arr[a]+d
  	else:
  		arr[a]=arr[b]-d
  	mem[a]=1
  	mem[b]=1
  else:
    if tmp!=d:
      flag=False
      break
if flag:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[0]*(n+1)
mem=[0]*(n+1)
job=[]
for _ in range(m):
  a,b,d=map(int,input().split())
  if a<=b:
    job.append([a,b,d])
  else:
    job.append([b,a,-d])
job=sorted(job,key=lambda x:x[1])
job=sorted(job,key=lambda x:x[0])
flag=True
for i in range(m):
  a=job[i][0]
  b=job[i][1]
  d=job[i][2]
  tmp=arr[b]-arr[a]
  if mem[a]*mem[b]==0:
  	if mem[b]==0:
  		arr[b]=arr[a]+d
  	else:
  		arr[a]=arr[b]-d
  	mem[a]=1
  	mem[b]=1
  else:
    if tmp!=d:
      flag=False
      break
print(arr)
if flag:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[0]*(n+1)
mem=[0]*(n+1)
job=[]
flag=True
for i in range(m):
  a,b,d=map(int,input().split())
  if a<=b:
  	job.append([a,b,d])
  else:
  	job.append([b,a,-d])
job=sorted(job, key=lambda x:x[0])
for i in range(m):
  a=job[i][0]
  b=job[i][1]
  d=job[i][2]
  tmp=abs(arr[b]-arr[a])
  if mem[a]*mem[b]==0:
  	if mem[b]==0:
  		arr[b]=arr[a]+d
  	else:
  		arr[a]=arr[b]-d
  	mem[a]=1
  	mem[b]=1
  else:
    if tmp!=abs(d):
      flag=False
      break
if flag:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

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 n<N and not s:  
  if not memo:    
    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: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
if M==0:
    print("Yes")
    quit()
G=[[] for i in range(N)]
K=[[] 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=[-1]*N
y=[1]*N
stack=deque()
for i in range(N):
    if y[i]:
        stack.extend(G[i])
        stack.extend(K[i])
        y[i]=0
    if len(stack)==0:
        continue
    while(stack):

        l,r,d=stack.popleft()

        if x[l]==-1:
            x[l]=0
        if x[r]==-1:
            x[r]=x[l]+d
            continue
        if x[r]!=x[l]+d:
            print("No")
            quit()
        stack.extend(G[r])
        stack.extend(K[r])
        y[r]=0
if max(x)-min(x)>10**9:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

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))
x=[-1]*N
y=[1]*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]==-1:
            x[l]=0
        if x[r]==-1:
            x[r]=x[l]+d
            continue
        if x[r]!=x[l]+d:
            print("No")
            quit()
        stack.extend(G[r])
        y[r]=0
if max(x)>10**9:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

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

N,M=map(int,input().split())
if M==0:
    print("Yes")
    quit()
G=[]
append=G.append
for i in range(M):
    append(tuple(map(int,input().split())))
G.sort()
x=[-1]*N
for l,r,d in G:
    l-=1
    r-=1
    if x[l]==-1:
        x[l]=0
    if x[r]==-1:
        x[r]=x[l]+d
        continue
    if x[r]!=x[l]+d:
        print("No")
        quit()
if max(x)>10**9:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

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

N,M=map(int,input().split())
if M==0:
    print("Yes")
    quit()
G=[]
append=G.append
for i in range(M):
    append(tuple(map(int,input().split())))
G.sort()
x=[-1]*N
for l,r,d in G:
    l-=1
    r-=1
    if x[l]==-1:
        x[l]=0
    if x[r]==-1:
        x[r]=x[l]+d
        continue
    if x[r]!=x[l]+d:
        print("No")
        quit()
if max(x)>10**9:
    print("No")
else:
    print("Yes")
print(x)

Submission status: Wrong Answer

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

N,M=map(int,input().split())
if M==0:
    print("Yes")
    quit()
G=[]
append=G.append
for i in range(M):
    append(tuple(map(int,input().split())))
G.sort()
x=[-1]*N
x[G[0][0]-1]=0
for l,r,d in G:
    l-=1
    r-=1
    if x[r]==-1:
        x[r]=x[l]+d
        continue
    if x[r]!=x[l]+d:
        print("No")
        quit()
if max(x)-min(x)>10**9:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
LRD=list(list(map(int,input().split())) for _ in range(M))
L=['#']*(N+1)
for _ in range(2):
    for l,r,d in LRD:
        if L[l]=='#'and L[r]=='#':
            L[l]=0;L[r]=d
        elif L[l]=='#' and L[r]!='#':
            L[l]=L[r]-d
        elif L[l]!='#' and L[r]=='#':
            L[r]=L[l]+d
        else:
            L[r]=L[l]+d
for l,r,d in LRD:
    if L[r]!=L[l]+d:
        print('No')
        exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
LRD=list(list(map(int,input().split())) for _ in range(M))
L=['#']*(N+1)
for _ in range(2):
    for l,r,d in LRD:
        if L[l]=='#'and L[r]=='#':
            L[l]=0;L[r]=d
        elif L[l]=='#' and L[r]!='#':
            L[l]=L[r]-d
        elif L[l]!='#' and L[r]=='#':
            L[r]=L[l]+d
        else:
            L[r]=L[l]+d
            L[l]=L[r]-d
for l,r,d in LRD:
    if L[r]!=L[l]+d:
        print('No')
        exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
LRD=list(list(map(int,input().split())) for _ in range(M))
L=['#']*(N+1)
for l,r,d in LRD:
    if L[l]=='#'and L[r]=='#':
        L[l]=0;L[r]=d
    elif L[l]=='#' and L[r]!='#':
        L[l]=L[r]-d
    elif L[l]!='#' and L[r]=='#':
        L[r]=L[l]+d
    else:
        if L[r]-L[l]!=d:
            print('No')
            exit()
print('Yes')

Submission status: Wrong Answer

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
d[0][0]=0
renketu=[]
checked=set([i for i in range(n)])
while(checked):
  p=checked.pop()
  s={p}
  q=[p]
  while(q):
    q_=q.pop(0)
    for x in d[q_][1]:
      if x in checked:
        checked.remove(x)
        s.add(x)
        q.append(x)
  renketu.append(s)
for ren in renketu:
  first=True
  while(ren and f):
    if first:
      p=ren.pop()
      d[p][0]=0
      first=False
    else:
      p=ren.pop()
    l=d[p]
    a=l[0]
    dic=l[1]
    for x in l[1]:
      if d[x][0]==-float('inf'):
        d[x][0]=a+dic[x]
      else:
        if d[x][0]!=a+dic[x]:
          f=False
          break
    else:
      continue
    break
  if f:
    continue
  break
print('Yes' if f else 'No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
d={i:[-1,{}] 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
d[0][0]=0
for i in range(n):
  l=d[i]
  a=l[0]
  dic=l[1]
  for x in l[1]:
    if d[x][0]==-1:
      if i<x:
        d[x][0]=a+dic[x]
      else:
        d[x][0]=a-dic[x]
    else:
      if i<x:
        if d[x][0]!=a+dic[x]:
          f=False
          break
      else:
        if d[x][0]!=a-dic[x]:
          f=False
          break
  else:
    continue
  break
print('Yes' if f else 'No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
d={i:[-1,{}] 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
d[0][0]=0
for i in range(n):
  l=d[i]
  a=l[0]
  dic=l[1]
  for x in l[1]:
    if d[x][0]==-1:
      d[x][0]=a+dic[x]
    else:
      if i<x:
        if d[x][0]!=a+dic[x]:
          f=False
          break
      else:
        if d[x][0]!=a-dic[x]:
          f=False
          break
  else:
    continue
  break
print('Yes' if f else 'No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
d={i:[-1,{}] 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
d[0][0]=0
for i in range(n):
  l=d[i]
  a=l[0]
  dic=l[1]
  for x in l[1]:
    if d[x][0]==-1:
      d[x][0]=a+dic[x]
    else:
      if abs(d[x][0]-a)!=dic[x]:
        f=False
        break
  else:
    continue
  break
print('Yes' if f else 'No')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections

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

def get_dist(l,r,graph,prev,cur_dis):
    if l == r:
        return cur_dis
    elif l not in graph:
        return None
    else:
        for k,v in graph[l].items():
            if k != prev:
                dis = get_dist(k,r,graph,l,cur_dis+v)
                if dis is not None:
                    return dis
    return None


def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    graph = collections.defaultdict(dict)
    pos = {}

    for l, r, d in zip(L,R,D):
        graph[l][r] = d
        graph[r][l] = -d

"""
    for l, r, d in zip(L,R,D):
        dd = get_dist(l, r, graph, l, 0)
        if dd is not None and dd != d:
            print(NO)
            return

    print(YES)
    return
"""


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Wrong Answer

Solution code:
if __name__ == "__main__":
    _, M = map(int, input().split())

    rel = {}
    is_ok = True
    for _ in range(M):
        a, b, d = map(int, input().split())
        
        if a not in rel:
            rel[a] = {}

        if b not in rel[a]:
            rel[a][b] = d

            if b in rel:
                for b_rl in rel[b]:
                    rel[a][b_rl] = rel[b][b_rl] + d
                    
        elif rel[a][b] != d:
            is_ok = False


        
        if b not in rel:
            rel[b] = {}

        if a not in rel[b]:
            rel[b][a] = d

            if a in rel:
                for a_rl in rel[a]:
                    rel[b][a_rl] = rel[a][a_rl] + d
                    
        elif rel[b][a] != d:
            is_ok = False

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
if m == 0:
    print('Yes')
    exit(0)
g = {i: [] for i 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]
s = set()
while stack:
    d = stack.pop()
    if d in s:
        continue
    for node, cost in g[d]:
        if l[node] == None:
            l[node] = l[d] + cost
        else:
            if l[node] != l[d] + cost:
                print('No')
                exit(0)
        stack.append(node)
    s.add(d)
print('Yes')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
g = {i: [] for i 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
l[0] = n
stack = [0]
s = set()
while stack:
    d = stack.pop()
    if d in s:
        continue
    for node, cost in g[d]:
        if l[node] == -1:
            l[node] = l[d] + cost
        else:
            if l[node] != l[d] + cost:
                print('No')
                exit()
        stack.append(node)
    s.add(d)
print('Yes')

Submission status: Wrong Answer

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]
    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: Wrong Answer

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)
        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):
        # 入力ノードのrootノードを見つける
        tmpx,tmpy=x,y
        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]=self.potential[tmpx]+d-self.potential[tmpy]

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.potential[x]=self.potential[tmpy]-d+self.potential[tmpx]
            # 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()
    elif not tree.isSameGroup(l,r): 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: Wrong Answer

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)
        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):
        # 入力ノードのrootノードを見つける
        tmpx,tmpy=x,y
        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]=self.potential[tmpx]+d-self.potential[tmpy]

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.potential[x]=self.potential[tmpy]-d+self.potential[tmpx]
            # 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: Wrong Answer

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)
        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):
        # 入力ノードのrootノードを見つける
        tmpx,tmpy=x,y
        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+self.potential[tmpx]

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.potential[x]=-d+self.potential[tmpy]
            # 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: Wrong Answer

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)
        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):
        # 入力ノードのrootノードを見つける
        tmpx,tmpy=x,y
        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+self.potential[tmpx]

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.potential[x]=-d+self.potential[tmpy]
            # 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)



print("Yes")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
LRD = []

for _ in range(m):
    l,r,d = map(int,input().split())
    LRD.append([min(l,r),max(l,r),d])
    
flag = True
from operator import itemgetter


LRD.sort(key = itemgetter(0))

dis = [0]*(n+1)

for l,r,d in LRD:
    if dis[r] == 0:
        dis[r] = d + dis[l]
    else:
        if dis[l] + d != dis[r]:
            flag = False
            break
if flag:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
x = [None] * N

for _ in range(M):
    l, r, d = map(int, input().split())
    if x[l-1] == None and x[r-1] == None:
        x[l-1] = 0
        x[r-1] = d
    elif x[l-1] == None:
        x[l-1] = x[r-1] - d
    elif x[r-1] == None:
        x[r-1] = d + x[l-1]
    else:
        if x[r-1] - x[l-1] != d:
            print('No')
            quit()
print('Yes')