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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, LRD):
    if M == 0:
        return 'Yes'
    g = defaultdict(dict)
    nr = set()
    for l, r, d in LRD:
        g[l][r] = d
        nr.add(r)

    r = set(range(1, N+1)) - nr
    r = list(r)
    while r:
        a = r.pop()
        s = [(0, a)]
        memo = {a: 0}
        while s:
            d, u = heapq.heappop(s)
            for v, dd in g[u].items():
                if v in memo:
                    if memo[v] != dd+d:
                        return 'No'
                else:
                    memo[v] = d+dd
                    heapq.heappush(s, (dd+d, v))
    if set(memo.keys()) != set(range(1, N+1)):
        return 'No'
    return 'Yes'







def main():
    N, M = read_int_n()
    LRD = [read_int_n() for _ in range(M)]
    print(slv(N, M, LRD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class WeightedDSU():
    def __init__(self, n):
        self.n = n
        self.par_size = [-1] * n
        self.wt = [0] * n

    def leader(self, a):
        #assert 0 <= a < self.n
        x = a
        while self.par_size[x] >= 0:
            x = self.par_size[x]
        return x

    def same(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        return self.leader(a) == self.leader(b)

    def merge(self, a, b, w):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        w += self.wt[a] - self.wt[b]
        x = self.leader(a)
        y = self.leader(b)
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]:
            x, y = y, x
            w *= -1
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        self.wt[y] = w
        return x

    def diff(self, a, b):
        return self.wt[b] - self.wt[a]

import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
wdsu = WeightedDSU(N)

for _ in range(M):
    l, r, d = map(int, input().split())
    if wdsu.same(l - 1, r - 1):
        if wdsu.diff(l - 1, r - 1) != d:
            print('No')
            break
    else:
        wdsu.merge(l - 1, r - 1, d)
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
class WeightedDSU():
    def __init__(self, n):
        self.n = n
        self.par_size = [-1] * n
        self.wt = [0] * n

    def leader(self, a):
        #assert 0 <= a < self.n
        x = a
        order = [x]
        while self.par_size[x] >= 0:
            x = self.par_size[x]
            order.append(x)
        for s in order[:-1][::-1]:
            self.wt[s] += self.wt[self.par_size[s]]
        while self.par_size[a] >= 0:
            self.par_size[a] = x
            a = self.par_size[a]
        return x

    def same(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        return self.leader(a) == self.leader(b)

    def merge(self, a, b, w):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        w += self.wt[a] - self.wt[b]
        x = self.leader(a)
        y = self.leader(b)
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]:
            x, y = y, x
            w *= -1
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        self.wt[y] = w
        return x

    def diff(self, a, b):
        return self.wt[b] - self.wt[a]

import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
wdsu = WeightedDSU(N)

for _ in range(M):
    l, r, d = map(int, input().split())
    if wdsu.same(l - 1, r - 1):
        if wdsu.diff(l - 1, r - 1) != d:
            print('No')
            break
    else:
        wdsu.merge(l - 1, r - 1, d)
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
n,m = ma()
use=[False]*n
INF=10**15
x = [INF]*n
ed=[]
for i in range(m):
    l,r,d=ma()
    if r>l:
        ed.append((l-1,r-1,d))
    else:
        ed.append((r-1,l-1,-d))

ed.sort()
ed.sort(key=lambda x:x[1])
f=True
for l,r,d in ed:
    if x[l]==INF and x[r]==INF:
        x[l]=0
        x[r]=d
    elif x[l]==INF:
        x[l]=x[r]-d
    elif x[r]==INF:
        x[r]=x[l]+d
    else:
        if x[r]-x[l]!=d:
            f=False
            break
yn(f)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
n,m = ma()
use=[False]*n
INF=10**15
x = [INF]*n
ed=[]
for i in range(m):
    l,r,d=ma()
    ed.append((l-1,r-1,d))

ed.sort()
f=True
for l,r,d in ed:
    if x[l]==INF and x[r]==INF:
        x[l]=0
        x[r]=d
    elif x[l]==INF:
        x[l]=x[r]-d
    elif x[r]==INF:
        x[r]=x[l]+d
    else:
        if x[r]-x[l]!=d:
            f=False
            break
yn(f)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N, M = map(int, input().split())
LRD = []
for _ in range(M):
    l, r, d = map(int, input().split())
    LRD.append([l, r, d])

# L,Rでソート
LRD.sort(key=itemgetter(0, 1))
# print(LRD)

nums = [-1] * (N + 1)
# nums[LRD[0][0]] = 0

for q in LRD:
    l = q[0]
    r = q[1]
    d = q[2]
    if nums[l] == -1:
        nums[l] = 0
    if nums[r] == -1:
        nums[r] = nums[l] + d
    else:
        if nums[r] == nums[l] + d:
            continue
        else:
            print("No")
            exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
n,m = map(int, input().split())
ml = [-1 for i in range(n)]

for i in range(m):
    l,r,d = map(int, input().split())
    l -= 1
    r -= 1
    if ml[l] == -1 and ml[r] == -1:
        ml[l] = 0
        ml[r] = d
    elif ml[l] != -1 and ml[r] == -1:
        ml[r] = d + ml[l]
        if ml[r] > n:
            print('No', flush=True)
            sys.exit()
    elif ml[l] == -1 and ml[r] != -1:
        ml[l] = ml[r] - d
        if ml[l] < 1:
            print('No', flush=True)
            sys.exit()
    else:
        if ml[r] - ml[l] != d:
            print('No', flush=True)
            sys.exit()

print('Yes', flush=True)

Submission status: Wrong Answer

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

for i in range(m):
    l,r,d = map(int, input().split())
    l -= 1
    r -= 1
    if ml[l] == -1 and ml[r] == -1:
        ml[l] = 0
        ml[r] = d
    elif ml[l] != -1 and ml[r] == -1:
        ml[r] = d + ml[l]
    elif ml[l] == -1 and ml[r] != -1:
        ml[l] = ml[r] - d
    else:
        if ml[r] - ml[l] != d:
            print('No', flush=True)
            import sys
            sys.exit()

print('Yes', flush=True)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
Loc_List = ["" for i  in range(N)]
flg = 0
for i in range(M):
    L,R,D = map(int,input().split())
    if (Loc_List[L-1] == "") and (Loc_List[R-1] == ""):
        Loc_List[R-1] = D
        Loc_List[L-1] = 0
    elif (Loc_List[L-1] != "") and (Loc_List[R-1] == ""):
        Loc_List[R-1] = Loc_List[L-1] + D
    elif (Loc_List[L-1] == "") and (Loc_List[R-1] != ""):
        Loc_List[L-1] = Loc_List[R-1] - D
    else:
        if (Loc_List[R-1]-Loc_List[L-1]) != D:
            flg = 1
        else:
            continue
    
print(("Yes","No")[flg > 0])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0] * M
root = [-float("inf")] * N
for i in range(M):
  l, r, d = map(int, input().split())
  if (root[l - 1] < - 10 ** 10) and (root[r - 1] < -10 ** 10):
    root[l - 1] = 0
    root[r - 1] = root[l - 1] + d
  elif root[l - 1] < - 10 ** 10:
    root[l - 1] = root[r - 1] - d
  else:
    root[r - 1] = root[l - 1] + d
  A[i] = [l, r, d]
      
for i in range(M):
  now = A[i]
  if root[now[1] - 1] - root[now[0] - 1] != now[2]:
    print("No")
    quit()
    
print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0] * M
root = [0] * N
for i in range(M):
  l, r, d = map(int, input().split())
  root[r - 1] = root[l - 1] + d
  A[i] = [l, r, d]
      
for i in range(M):
  now = A[i]
  if root[now[1] - 1] - root[now[0] - 1] != now[2]:
    print("No")
    quit()
    
print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0] * M
root = [0] * N
for i in range(M):
  l, r, d = map(int, input().split())
  root[r - 1] = root[l - 1] + d
  A[i] = [l, r, d]
  
if min(root) < 0:
  nn = min(root)
  for i in range(N):
    root[i] += -nn
  if max(root) > 10 ** 9:
    print("No")
    quit()
elif max(root) > 10 ** 9:
  nn = max(root) - 10 ** 9
  for i in rangE(N):
    root[i] -= nn
  if min(root) < 0:
    print("No")
    quit()
    
for i in range(M):
  now = A[i]
  if root[now[1] - 1] - root[now[0] - 1] != now[2]:
    print("No")
    quit()
    
print("Yes")

Submission status: Wrong Answer

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
            return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx,_=self.find(x)
        ry,_=self.find(y)
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.dist[x]+=max(0,self.dist[self.parents[x]])
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)
        ry=self.find(y)
        diff=max(0,self.dist[y])-max(0,self.dist[x])-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],-diff+self.parents[rx])
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
    def showdist(self):
        retrun 
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d-1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.dist[x]+=max(0,self.dist[self.parents[x]])
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)
        ry=self.find(y)
        diff=max(0,self.dist[y])-max(0,self.dist[x])-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],-diff+self.parents[rx])
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
    def showdist(self):
        retrun 
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d+1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.dist[x]+=max(0,self.dist[self.parents[x]])
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)
        ry=self.find(y)
        diff=max(0,self.dist[x])-max(0,self.dist[y])-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[rx]=min(self.parents[rx],-diff+self.parents[ry])
        self.parents[ry]=rx
        self.dist[ry]=diff
        return False
    
    def showdist(self):
        retrun 
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d+1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            self.dist[x]+=self.dist[self.parents[x]]
            return self.parents[x]
    
    def union(self,x,y,d):
        diff=self.dist[x]-self.dist[y]-d
        x=self.find(x)
        y=self.find(y)
        if x==y:
            if diff!=0:
                return True
            return False
        if diff<0:
            x,y=y,x
            diff=-diff
        self.parents[x]=min(self.parents[x],-diff+self.parents[y])
        self.parents[y]=x
        self.dist[y]=diff
        return False
    
    def showdist(self):
        retrun 
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d+1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n
        self.ranks=[0]*n
    
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            self.dist[x]+=self.dist[self.parents[x]]
            return self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)
        ry=self.find(y)
        if rx==ry:
            if self.dist[x]!=self.dist[y]+d:
                return True
            return False
        if self.ranks[rx]>self.ranks[ry]:
            x,y=y,x
            rx,ry=ry,rx
            d=-d
        self.dist[rx]=d+self.dist[y]-self.dist[x]
        self.parents[rx]=ry
        if self.ranks[rx]==self.ranks[ry]:
            self.ranks[ry]+=1
        return False
    
    def showroots(self):
        return [i for i,p in enumerate(self.parents) if p<0]

    def totdist(self):
        roots=self.showroots()
        nr=len(roots)
        posdist=[0 for _ in range(nr)]
        negdist=[0 for _ in range(nr)]
        for i,v in enumerate(self.dist):
            ri=self.find(i)
            idx=roots.index(ri)
            posdist[idx]=max([posdist[idx],self.dist[i],0])
            negdist[idx]=min([negdist[idx],self.dist[i],0])
        return dict((x,pos-neg) for x,pos,neg in zip(roots,posdist,negdist))
def main():
    n,m,*lrd=map(int,read().split())
    edg=[]
    for l,r,d in zip(*[iter(lrd)]*3):
        if l>r:
            edg.append((r-1,l-1,-d))
        else:
            edg.append((l-1,r-1,d))
    v=Unionfind(n)
    for e in edg:
        if v.union(*e):
            print('No')
            break
    else:
        dd=v.totdist()
        for d in iter(dd):
            if d>10**9:
                print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*n
        self.dist=[0]*n
    
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            self.dist[x]+=self.dist[self.parents[x]]
            return self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)
        ry=self.find(y)
        if rx==ry:
            if self.dist[x]!=self.dist[y]+d:
                return True
            return False
        if self.ranks[rx]>self.ranks[ry]:
            x,y=y,x
            rx,ry=ry,rx
            d=-d
        self.dist[rx]=d+self.dist[y]-self.dist[x]
        self.parents[rx]=ry
        if self.ranks[rx]==self.ranks[ry]:
            self.ranks[ry]+=1
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    edg=[]
    for l,r,d in zip(*[iter(lrd)]*3):
        if l>r:
            edg.append((r-1,l-1,-d))
        else:
            edg.append((l-1,r-1,d))
    v=Unionfind(n)
    for e in edg:
        if v.union(*e):
            print('No')
            break
    else:
        if max(v.dist)-min(v.dist)>10**9:
          print('No')
        else:
          print('Yes')
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*n
        self.dist=[0]*n
    
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            self.dist[x]+=self.dist[self.parents[x]]
            return self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)
        ry=self.find(y)
        if rx==ry:
            if self.dist[x]!=self.dist[y]+d:
                return True
            return False
        if self.ranks[rx]>self.ranks[ry]:
            x,y=y,x
            rx,ry=ry,rx
            d=-d
        self.dist[rx]=d+self.dist[y]-self.dist[x]
        self.parents[rx]=ry
        if self.ranks[rx]==self.ranks[ry]:
            self.ranks[ry]+=1
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    edg=[]
    for l,r,d in zip(*[iter(lrd)]*3):
        if l>r:
            edg.append((r-1,l-1,-d))
        else:
            edg.append((l-1,r-1,d))
    v=Unionfind(n)
    for e in edg:
        if v.union(*e):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*n
        self.dist=[0]*n
    
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            self.dist[x]+=self.dist[self.parents[x]]
            return self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)
        ry=self.find(y)
        if rx==ry:
            if self.dist[x]!=self.dist[y]+d:
                return True
            return False
        if self.ranks[rx]>self.ranks[ry]:
            x,y=y,x
            rx,ry=ry,rx
            d=-d
        self.dist[rx]=d+self.dist[y]-self.dist[x]
        self.parents[rx]=ry
        if self.ranks[rx]==self.ranks[ry]:
            self.ranks[ry]+=1
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    edg=[]
    for l,r,d in zip(*[iter(lrd)]*3):
        if l>r:
            edg.append((r-1,l-1,-d))
        else:
            edg.append((l-1,r-1,d))
    print(edg)
    v=Unionfind(n)
    for e in edg:
        if v.union(*e):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n , m = map(int,input().split())
z = []
for i in range(m):
    l , r , d = map(int,input().split())
    z.append((l,r,d))
    z.append((r,l,-d))
z.sort()
INF = -10**10
kaku = [INF for i in range(n+1)]

for i in range(2*m):
    x , y , d = z[i]
    if kaku[x] == INF and kaku[y] == INF:
        kaku[x] = 0
        kaku[y] = d
    elif kaku[x] != INF and kaku[y] == INF:
        kaku[y] = kaku[x] + d
    elif kaku[x] == INF and kaku[y] != INF:
        kaku[x] = kaku[y] - d
    elif kaku[x] != INF and kaku[y] != INF:
        if kaku[y] - kaku[x] != d:
            print("No")
            exit()
saidai = -10**9 - 7
saisyo = 10**9 + 7
flag = True
for i in range(n+1):
    if kaku[i] != INF:
        flag = False
        saisyo = min(saisyo,kaku[i])
        saidai = max(saidai,kaku[i])
if saidai - saisyo > 10 ** 9 and not flag:
    print("No")
    exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
n , m = map(int,input().split())
z = []
for i in range(m):
    l , r , d = map(int,input().split())
    z.append((l,r,d))
    z.append((r,l,-d))
z.sort()
INF = -10**10
kaku = [INF for i in range(n+1)]

for i in range(2*m):
    x , y , d = z[i]
    if kaku[x] == INF and kaku[y] == INF:
        kaku[x] = 0
        kaku[y] = d
    elif kaku[x] != INF and kaku[y] == INF:
        kaku[y] = kaku[x] + d
    elif kaku[x] == INF and kaku[y] != INF:
        kaku[x] = kaku[y] - d
    elif kaku[x] != INF and kaku[y] != INF:
        if kaku[y] - kaku[x] != d:
            print("No")
            exit()
saidai = -10**9 - 7
saisyo = 10**9 + 7
for i in range(n+1):
    if kaku[i] != INF:
        saisyo = min(saisyo,kaku[i])
        saidai = max(saidai,kaku[i])
if saidai - saisyo > 10 ** 9:
    print("No")
    exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
n , m = map(int,input().split())
z = []
for i in range(m):
    l , r , d = map(int,input().split())
    z.append((l,r,d))
    z.append((r,l,-d))
z.sort()
kaku = [-1 for i in range(n+1)]

for i in range(2*m):
    x , y , d = z[i]
    if kaku[x] == -1 and kaku[y] == -1:
        kaku[x] = 0
        kaku[y] = d
    elif kaku[x] != -1 and kaku[y] == -1:
        kaku[y] = kaku[x] + d
    elif kaku[x] == -1 and kaku[y] != -1:
        kaku[x] = kaku[y] - d
    elif kaku[x] != -1 and kaku[y] != -1:
        if kaku[y] - kaku[x] != d:
            print("No")
            exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
n , m = map(int,input().split())
z = [tuple(map(int,input().split())) for i in range(m)]
z.sort()
kaku = [-1 for i in range(n+1)]

for i in range(m):
    x , y , d = z[i]
    if kaku[x] == -1 and kaku[y] == -1:
        kaku[x] = 0
        kaku[y] = d
    elif kaku[x] != -1 and kaku[y] == -1:
        kaku[y] = kaku[x] + d
    elif kaku[x] == -1 and kaku[y] != -1:
        kaku[x] = kaku[y] - d
    elif kaku[x] != -1 and kaku[y] != -1:
        if kaku[y] - kaku[x] != d:
            print("No")
            exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


INF = 10**17


def main():

    N, M = in_nn()
    LRD = in_nl2(M)

    edge = [[] for _ in range(N)]

    for i in range(M):
        l, r, d = LRD[i]
        l, r = l - 1, r - 1
        edge[l].append((r, d))
        edge[r].append((l, -d))

    v_set = []
    search = [False] * N

    def bfs(N, v0, edge):

        search[v0] = True
        q = deque()
        q.append(v0)

        while q:
            v = q.popleft()
            for nv, _ in edge[v]:
                if not search[nv]:
                    q.append(nv)
                    search[nv] = True

    for i in range(N):
        if not search[i]:
            bfs(N, i, edge)
            v_set.append(i)

    def judge(v0):

        search = defaultdict(lambda: False)
        search[v0] = True

        q = deque()
        q.append(v0)

        pos = defaultdict(lambda: INF)
        pos[v0] = 0

        vs = [v0]

        while q:
            v = q.popleft()
            now_pos = pos[v]
            for nv, dis in edge[v]:
                if pos[nv] == INF:
                    pos[nv] = now_pos + dis
                elif pos[nv] - now_pos != dis:
                    return False
                if not search[nv]:
                    q.append(nv)
                    search[nv] = True
                    vs.append(nv)

        max_pos = -INF
        min_pos = INF
        for tv in vs:
            tp = pos[tv]
            max_pos = max(max_pos, tp)
            min_pos = min(min_pos, tp)

        return max_pos - min_pos <= 10**9 + 1

    ans = 'YES'
    for v in v_set:
        if not judge(v):
            ans = 'NO'

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# D - People on a Line
import sys
sys.setrecursionlimit(10 ** 9)

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

INF = float('inf')
c = [INF for _ in range(n)]

def bfs(u,x):
  q = [(u,x)]
  while(q):
    qq = []
    u,x = q.pop()
    if c[u] != INF:
      if c[u] != x:
        print('No')
        exit()
    else:
      c[u] = x
    for v,d in e[u]:
      if c[v] != INF:
        if c[v] == c[u]+d:
          continue
      qq.append((v,c[u]+d))
    q = qq[:]

for i in range(n):
  if c[i] == INF:
    bfs(i,0)
print('Yes')

Submission status: Wrong Answer

Solution code:
# D - People on a Line
import sys
sys.setrecursionlimit(10 ** 9)

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

INF = float('inf')
c = [INF for _ in range(n)]

def bfs(u,x):
  q = [(u,x)]
  while(q):
    qq = []
    u,x = q.pop()
    c[u] = x
    for v,d in e[u]:
      if c[v] != INF:
        if c[v] == c[u]+d:
          continue
        else:
          print('No')
          exit()
      else:
        qq.append((v,c[u]+d))
    q = qq[:]

for i in range(n):
  if c[i] == INF:
    bfs(i,0)
print('Yes')

Submission status: Wrong Answer

Solution code:
# D - People on a Line
from heapq import heappush,heappop

n,m = map(int,input().split())
hq = []
for i in range(m):
  l,r,d = map(int,input().split())
  l -= 1
  r -= 1
  if l < r:
    heappush(hq,(l,r,d))
  else:
    heappush(hq,(r,l,-d))

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

INF = float('inf')
x = [INF for _ in range(n)]
for i in range(2):
  hq0 = hq[:]
  while(hq0):
    a,b,d = heappop(hq0)
    if x[a] == INF:
      x[a] = 0
    if x[b] == INF:
      x[b] = x[a]+d
    else:
      if x[b] != x[a]+d:
        print('No')
        #print(x)
        exit()
print('Yes')
# mn = INF
# mx = -INF
# for xi in x:
#   if xi != INF:
#     mn = min(xi,mn)
#     mx = max(xi,mx)
#print(mn,mx)
# if (mn == INF and mx == -INF) or mx-mn <= 10**9:
#   print('Yes')
# else:
#   print('No')
#print(x)