Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

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

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

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

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

D_i are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

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

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

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

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



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


Sample output:
Yes

Submission status: Time Limit Exceeded

Solution code:
(n, m) = [int(v) for v in input().split(' ')]

adj_matrix = [[None for i in range(n)] for j in range(n)]

flag = True

for i in range(m):
    (r, l, d) = [int(v) for v in input().split(' ')]
    if flag == False:
        continue
    if (adj_matrix[r-1][l-1] is not None) and (adj_matrix[r-1][l-1] != d):
        flag = False
    if (adj_matrix[l-1][r-1] is not None) and (adj_matrix[l-1][r-1] != -d):
        flag = False
    adj_matrix[r-1][l-1] = d
    adj_matrix[l-1][r-1] = -d
    for x in [r-1, l-1]:
        for y in [r-1, l-1]:
            if adj_matrix[x][y] is None:
                continue
            elif x == y:
                continue
            for z in range(n):
                if adj_matrix[x][z] is None:
                    continue
                elif y == z:
                    continue
                tmp_d = adj_matrix[x][z] - adj_matrix[x][y]
                if (adj_matrix[y][z] is not None) and (adj_matrix[y][z] != tmp_d):
                    flag = False
                else:
                    adj_matrix[y][z] = tmp_d
                if (adj_matrix[z][y] is not None) and (adj_matrix[z][y] != -tmp_d):
                    flag = False
                else:
                    adj_matrix[z][y] = -tmp_d

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, input().split())
Gr = {}
R = []
for i in range(m):
    l, r, d = map(int, input().split())
    Gr[(l - 1, r - 1)] = d
    Gr[(r - 1, l - 1)] = -d
    if l - 1 not in R:
        R.append(l - 1)
    if r - 1 not in R:
        R.append(r - 1)


for i in Gr:
    for k in R:
        if (i[0], k) in Gr and (k, i[1]) in Gr:
            if Gr[i] != Gr[(i[0], k)] + Gr[(k, i[1])]:
                print("No")
                sys.exit()

print("Yes")

Submission status: Time Limit Exceeded

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

L=[]
R=[]
D=[]
for i in range(M):
    l,r,d=map(int, input().split())
    L.append(l)
    R.append(r)
    D.append(d)

T=[]
X=[0]*N
for i in range(M):
    large=max(R[i],L[i])
    smal=min(R[i],L[i])
    if X[large-1]==0:
        X[large-1]=sum(X[0:smal])+D[i]
    elif X[large-1]!=0 and X[large-1]-X[smal-1]!=D[i]:
        T.append(i)

t=0
for i in T:
    large=max(R[i],L[i])
    smal=min(R[i],L[i])
    if X[large-1]!=0 and X[large-1]-X[smal-1]!=D[i]:
        t=1

if t==0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())
L = []
R = []
D = []
for i in range(M):
    k, l, m = map(int, input().split())
    L.append(k)
    R.append(l)
    D.append(m)

DP = [None] * 100001

inc = 0

ids = {}

for i, j, k in sorted(list(zip(L, R, D))):
    if DP[i] != None and DP[j] != None:
        if DP[i][1] != DP[j][1]:
            diff = (DP[i][0] + k) - DP[j][0]
            ids[DP[i][1]] += ids[DP[j][1]]
            for l in ids[DP[j][1]]:
                DP[l][0] += diff
                DP[l][1] = DP[i][1]
        if DP[i][1] == DP[j][1] and DP[j][0] != DP[i][0] + k:
            print('No')
            sys.exit()
    if DP[i] == None and DP[j] == None:
        DP[i] = [0, inc]
        DP[j] = [DP[i][0] + k, inc]
        ids[inc] = [i, j]
        inc += 1
    if DP[i] == None and DP[j] != None:
        DP[i] = [DP[j][0] - k, DP[j][1]]
        ids[DP[j][1]].append(i)
    if DP[i] != None and DP[j] == None:
        DP[j] = [DP[i][0] + k, DP[i][1]]
        ids[DP[i][1]].append(j)
    
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
Gr = {}
R = []
for i in range(m):
    l, r, d = map(int, input().split())
    Gr[(l - 1, r - 1)] = d
    Gr[(r - 1, l - 1)] = -d
    if l - 1 not in R:
        R.append(l - 1)
    if r - 1 not in R:
        R.append(r - 1)


rec = True
for i in Gr:
    for k in R:
        if (i[0], k) in Gr and (k, i[1]) in Gr:
            if Gr[i] != Gr[(i[0], k)] + Gr[(k, i[1])]:
                rec = False

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

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M=map(int,input().split())
if M==0:
  print('Yes')
  sys.exit()
people=N*[1145141919]
mlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  if L<R:
    mlist.append([L,R,D])
  else:
    mlist.append([R,L,(-1)*D])
mlist.sort()
people[mlist[0][0]-1]=0
people[mlist[0][1]-1]=mlist[0][2]
del mlist[0]
tmp1=-1
tmp2=-2
while True:
  if len(mlist)==0:break
  elif tmp1==tmp2:
    people[mlist[0][0]-1]=0
    people[mlist[0][1]-1]=mlist[0][2]
    del mlist[0]
  for i in mlist:
    if people[i[0]-1]!=1145141919 and people[i[1]-1]==1145141919:
      people[i[1]-1]=people[i[0]-1]+i[2]
      mlist.remove([i[0],i[1],i[2]])
    elif people[i[1]-1]!=1145141919 and people[i[0]-1]==1145141919:
      people[i[0]-1]=people[i[1]-1]-i[2]
      mlist.remove([i[0],i[1],i[2]])
    elif people[i[0]-1]!=1145141919 and people[i[1]-1]!=1145141919:
      if people[i[1]-1]-people[i[0]-1]!=i[2]:
        print('No')
        sys.exit()
      mlist.remove([i[0],i[1],i[2]])
  tmp1=tmp2
  tmp2=len(mlist)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, raw_input().split())

mat = list()
co_mat = list()
for _ in xrange(M):
    l, r, d = map(int, raw_input().split())
    vec = [0 for _ in xrange(N)]
    vec[l - 1] = 1
    vec[r - 1] = -1
    mat.append(vec)

    co_vec = vec[:]
    co_vec.append(d)
    co_mat.append(co_vec)

mat = np.array(mat)
co_mat = np.array(co_mat)

if np.linalg.matrix_rank(mat) == np.linalg.matrix_rank(co_mat):
    print "Yes"
else:
    print "No"

Submission status: Time Limit Exceeded

Solution code:
(n, m) = [int(v) for v in input().split(' ')]

adj_matrix = [[None for i in range(n)] for j in range(n)]

flag = True

for i in range(m):
    (r, l, d) = [int(v) for v in input().split(' ')]
    if flag == False:
        continue
    if (adj_matrix[r-1][l-1] is not None) and (adj_matrix[r-1][l-1] != d):
        flag = False
    if (adj_matrix[l-1][r-1] is not None) and (adj_matrix[l-1][r-1] != -d):
        flag = False
    adj_matrix[r-1][l-1] = d
    adj_matrix[l-1][r-1] = -d
    for x in [r-1, l-1]:
        for y in range(n-1):
            if adj_matrix[x][y] is None:
                continue
            for z in range(y+1, n):
                if adj_matrix[x][z] is None:
                    continue
                tmp_d = adj_matrix[x][z] - adj_matrix[x][y]
                if (adj_matrix[y][z] is not None) and (adj_matrix[y][z] != tmp_d):
                    flag = False
                else:
                    adj_matrix[y][z] = tmp_d
                if (adj_matrix[z][y] is not None) and (adj_matrix[z][y] != -tmp_d):
                    flag = False
                else:
                    adj_matrix[z][y] = -tmp_d

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
Gr = {}
R = []
for i in range(m):
    l, r, d = map(int, input().split())
    Gr[(l - 1, r - 1)] = d
    Gr[(r - 1, l - 1)] = -d


rec = True
for i in Gr:
    for k in range(i[0], i[1]):
        if (i[0], k) in Gr and (k, i[1]) in Gr:
            if Gr[i] != Gr[(i[0], k)] + Gr[(k, i[1])]:
                rec = False

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = [int(a) for a in input().split()]
LRD_ = []
for i in range(M):
    LRD_.append([int(a) for a in input().split()])

LRD = sorted(LRD_)

if M == 0 or N == 1:
    print("Yes")
    exit(0)

len_na = 0

while True:
    not_appear = []
    if len_na == len(not_appear):
        place = np.ones(N+1) * -1
        l,r,d = LRD.pop(0)
        place[l] = 0
        place[r] = place[l] + d
        len_na = len(not_appear)
    for l, r, d in LRD:
        if place[l] == -1 and place[r] == -1:
            not_appear.append((l, r, d))
            continue
        if place[r] == -1:
            place[r] = place[l] + d
            continue
        if place[l] == -1:
            place[l] = place[r] - d
            continue
        if place[r] != place[l] + d:
            print("No")
            exit(0)
    LRD = not_appear
    if LRD == []:
        break

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
x = {}
n, m = map(int, raw_input().split())
flag = True
for _ in xrange(m):
    l, r, d = map(int, raw_input().split())
    if l in x:
        if r in x:
            if x[l][1] + d != x[r][1]:
                if x[l][0] == x[r][0]:
                    flag = False
                else:
                    for k, v in x.iteritems():
                        if v[0] == r:
                            x[k] = (x[l][0], v[1] + x[l][1] + d)
        else:
            x[r] = (x[l][0], x[l][1] + d)
    else:
        x[l], x[r] = (l, 0), (l, d)
print 'Yes' if flag else 'No'

Submission status: Time Limit Exceeded

Solution code:
(n, m) = [int(v) for v in input().split(' ')]

adj_matrix = [[None for i in range(n)] for j in range(n)]

flag = True

for i in range(m):
    (r, l, d) = [int(v) for v in input().split(' ')]
    if (adj_matrix[r-1][l-1] is not None) and (adj_matrix[r-1][l-1] != d):
        flag = False
        break
    if (adj_matrix[l-1][r-1] is not None) and (adj_matrix[l-1][r-1] != -d):
        flag = False
        break
    adj_matrix[r-1][l-1] = d
    adj_matrix[l-1][r-1] = -d
    for x in range(n):
        for y in range(n-1):
            if adj_matrix[x][y] is None:
                continue
            for z in range(y+1, n):
                if adj_matrix[x][z] is None:
                    continue
                tmp_d = adj_matrix[x][z] - adj_matrix[x][y]
                if (adj_matrix[y][z] is not None) and (adj_matrix[y][z] != tmp_d):
                    flag = False
                else:
                    adj_matrix[y][z] = tmp_d
                if (adj_matrix[z][y] is not None) and (adj_matrix[z][y] != -tmp_d):
                    flag = False
                else:
                    adj_matrix[z][y] = -tmp_d
    if flag == False:
        break

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

Submission status: Time Limit Exceeded

Solution code:
N_PEOPLE, N_INFO = list(map(int, input().split()))

info_list = []
for i in range(N_INFO):
  l, r, d = list(map(int, input().split()))
  info_list.append({
    "left":  l-1,
    "right": r-1,
    "dist":  d
  })

# 与えられた条件を満たす場合があるか
fulfill_conditions = True

# 各人の位置(不定の場合は-1)
locations = [-1] * N_PEOPLE

# 各人が登場したか
appeared = []

# 各人の関係グラフ
relation = []
for i in range(N_PEOPLE):
  relation.append([])
  for j in range(N_PEOPLE):
    relation[i].append(False)

for info in info_list:
  # 左右の人物が共に初登場なら，とりあえずleftを0において，rightを距離の分だけ離す
  if info["left"] not in appeared and info["right"] not in appeared:
    locations[info["left"]] = 0
    locations[info["right"]] = info["dist"]

    appeared.append(info["left"])
    appeared.append(info["right"])

    relation[info["left"]][info["right"]] = True
    relation[info["right"]][info["left"]] = True

    continue

  # 左の人物だけが初登場なら，rightの人物の位置から見てdist分左におく
  if info["left"] not in appeared and info["right"] in appeared:
    locations[info["left"]] = locations[info["right"]] - info["dist"]

    # 左に置くと範囲外になるなら，それを0に設置して，
    # 超過した分だけ他の人を右にずらす
    if locations[info["left"]] < 0:
      exceeded_dist = -1 * locations[info["left"]]
      locations[info["left"]] = 0

      for index, is_related in enumerate(relation[info["right"]]):
        if is_related:
          locations[index] += exceeded_dist

      if max(locations) > 10**9:
        fulfill_conditions = False
        break

    appeared.append(info["left"])

    relation[info["left"]][info["right"]] = True
    relation[info["right"]][info["left"]] = True

    continue


  # 右の人物だけが初登場なら，leftの人物から見てdist分右におく
  if info["left"] in appeared and info["right"] not in appeared:
    locations[info["right"]] = locations[info["left"]] + info["dist"]

    # 右に置くと範囲外になるなら，それを10**9に設置して，
    # 超過した分だけ他の人を左にずらす
    if locations[info["right"]] > 10**9:
      exceeded_dist = locations[info["right"]] - (10**9)
      locations[info["right"]] = 10**9

      for index, is_related in enumerate(relation[info["left"]]):
        if is_related:
          locations[index] += exceeded_dist

      if min(locations) < 0:
        fulfill_conditions = False
        break

    appeared.append(info["right"])

    relation[info["left"]][info["right"]] = True
    relation[info["right"]][info["left"]] = True

    continue

  # 両方の人物が既出なら，距離が正しいかチェックする
  # 正しくなければアウト
  if info["left"] in appeared and info["right"] in appeared:
    if locations[info["right"]] - locations[info["left"]] != info["dist"]:

      fulfill_conditions = False
      break

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

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M=map(int,input().split())
if M==0:
  print('Yes')
  sys.exit()
people=N*[1145141919]
mlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  mlist.append([L,R,D])
people[mlist[0][0]-1]=0
people[mlist[0][1]-1]=mlist[0][2]
del mlist[0]
tmp1=-1
tmp2=-2
while True:
  if len(mlist)==0:break
  elif tmp1==tmp2:
    people[mlist[0][0]-1]=0
    people[mlist[0][1]-1]=mlist[0][2]
    del mlist[0]
  for i in mlist:
    if people[i[0]-1]!=1145141919 and people[i[1]-1]==1145141919:
      people[i[1]-1]=people[i[0]-1]+i[2]
      mlist.remove([i[0],i[1],i[2]])
    elif people[i[1]-1]!=1145141919 and people[i[0]-1]==1145141919:
      people[i[0]-1]=people[i[1]-1]-i[2]
      mlist.remove([i[0],i[1],i[2]])
    elif people[i[1]-1]!=1145141919 and people[i[0]-1]!=1145141919:
      if people[i[1]-1]-people[i[0]-1]!=i[2]:
        print('No')
        sys.exit()
      mlist.remove([i[0],i[1],i[2]])
  tmp1=tmp2
  tmp2=len(mlist)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8

line = input().split(" ")
N = int(line[0])
M = int(line[1])

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

l = []
for _ in range(M):
    line = input().split(" ")
    l.append((
        int(line[0])-1
        ,int(line[1])-1
        ,int(line[2])
    ))
l.sort()
o = l[0][0]
for i in range(M):
    l[i] = (
        l[i][0]-o
        ,l[i][1]-o
        ,l[i][2]
    )

nl = [-1 for x in range(N)]
nl[0] = 0

flag = True
while flag:
    flag = False
    ll = []
    for c in l:
        if nl[c[0]]>=0 and nl[c[1]]==-1:
            nl[c[1]] = nl[c[0]]+c[2]
        elif nl[c[0]]==-1 and nl[c[1]]>=0:
            nl[c[0]] = nl[c[1]]-c[2]
        elif nl[c[0]]>=0 and nl[c[1]]>=0:
            if nl[c[1]]-nl[c[0]]==c[2]:
                pass
            else:
                print("No")
                exit()
        else:
            ll.append(c)
            flag = True
    l = ll.copy()

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = [int(a) for a in input().split()]
LRD_ = []
for i in range(M):
    l, r, d = [int(a) for a in input().split()]
    if l < r:
        LRD_.append((l, r, d))
    else:
        LRD_.append((r, l, -d))

LRD = sorted(LRD_)

if M == 0 or N == 1:
    print("Yes")
    exit(0)

while LRD != []:
    not_appear = []
    place = np.ones(N+1) * -1
    l,r,d = LRD.pop(0)
    place[l] = 0
    place[r] = place[l] + d
    for l, r, d in LRD:
        if place[l] == -1 and place[r] == -1:
            not_appear.append((l, r, d))
            continue
        if place[r] == -1:
            place[r] = place[l] + d
            continue
        if place[l] == -1:
            place[l] = place[r] - d
            continue
        if place[r] != place[l] + d:
            print("No")
            exit(0)
    LRD = not_appear

print("Yes")

Submission status: Time Limit Exceeded

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())
#	print(L[i],R[i],D[i])
leftside = 0
cand = set()
for i in range(M):
	cand.add(L[i])
for i in range(M):
	if R[i] in cand:
		cand.remove(R[i])

res = True
if M == 0:
	res = True
else:
	if len(cand) == 0:
		res = False
	else:
		leftside = list(cand)
#		print("leftside:",leftside)
		ok = True
		for c in leftside:
			point = [-1] * (N+1)
			point[c] = 0
			ok = True
			while True:
				update = False
				for i in range(M):
					if point[L[i]] != -1:
						if point[R[i]] == -1:
							update = True
							point[R[i]] = point[L[i]] + D[i]
						else:
							if point[R[i]] != point[L[i]] + D[i]:
								ok = False
								break
				if update == False:
					break
				res &= ok
					
print("Yes" if res == True else "No")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import itertools

N,M = [int(i) for i in input().split()]

L=[]
R=[]
D=[]
for i in range(M):
    l,r,d = [int(i) for i in input().split()]
    L.append(l-1)
    R.append(r-1)
    D.append(d)

position = [0]*N
color = [0]*N
cnum = 0
flag = 0
for i in range(M):
    if color[L[i]] == 0 and color[R[i]] == 0:
        position[L[i]] = 0
        position[R[i]] = D[i]
        cnum += 1
        color[L[i]] = cnum
        color[R[i]] = cnum
    elif color[L[i]] == 0 and color[R[i]] != 0:
        position[L[i]] = position[R[i]]-D[i]
        color[L[i]] = color[R[i]]
    elif color[L[i]] != 0 and color[R[i]] == 0:
        position[R[i]] = position[L[i]]+D[i]
        color[R[i]] = color[L[i]]
    elif color[L[i]] != 0 and color[R[i]] != 0:
        if color[R[i]] != color[L[i]]:
            syuusei = position[R[i]] - position[L[i]] - D[i]
            rc = color[R[i]]
            lc = color[L[i]]
            for i in range(N):
                if color[i] == rc:
                    color[i] = lc
                    position[i] -= syuusei
        else:
            if position[R[i]] - position[L[i]] != D[i]:
                flag = 1
                break

if flag ==1:
    print('No')
else:
    print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
Gr = defaultdict(int)
for i in range(m):
    l, r, d = map(int, input().split())
    Gr[(l - 1, r - 1)] = d
    Gr[(r - 1, l - 1)] = -d


rec = True
for i in range(n):
    for j in range(n):
        for k in range(n):
            if (i, j) in Gr and (i, k) in Gr and (k, j) in Gr:
                if Gr[(i, j)] != Gr[(i, k)] + Gr[(k, j)]:
                    rec = False

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

Submission status: Accepted

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.rank = [0] * n
        self.weight = [0] * n
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y
    def unite(self, x, y, w):
        p, q = self.find(x), self.find(y)
        if self.rank[p] < self.rank[q]:
            self.par[p] = q
            self.weight[p] = w - self.weight[x] + self.weight[y]
        else:
            self.par[q] = p
            self.weight[q] = -w - self.weight[y] + self.weight[x]
            if self.rank[p] == self.rank[q]:
                self.rank[p] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
n, m = map(int, input().split())
UF = WeightedUnionFind(n)
for i in range(m):
    l, r, d = map(int, input().split())
    if UF.same(l - 1, r - 1):
        if UF.diff(l - 1, r - 1) != d:
            exit(print("No"))
    else:
        UF.unite(l - 1, r - 1, d)
print("Yes")

Submission status: Accepted

Solution code:
class DSUWeighted():
    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]]
            self.par_size[s] = 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
        x = self.leader(a)
        y = self.leader(b)
        w += self.wt[a] - self.wt[b]
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]:
            x, y = y, x
            w = -w
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        self.wt[y] = w
        return x

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

import sys
input = sys.stdin.buffer.readline

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

uf = DSUWeighted(N)

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

Submission status: Accepted

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()

INF=10**15
x = [INF]*n
tree = [[] for i in range(n)]

for i in range(m):
    l,r,d=ma()
    tree[l-1].append((r-1,d))
    tree[r-1].append((l-1,-d))
f=True
def dfs(s):
    stack = collections.deque()
    stack.append((s,0))
    x[s]=0
    ret=True
    while stack:
        pre,c = stack.pop()
        for nex,d in tree[pre]:
            if x[nex]==INF:
                x[nex]=c+d
                stack.append((nex,c+d))
            else:
                if x[nex] !=c+d:
                    # print("pre,nex",pre,nex,x,c,d)
                    ret=False
    return ret
f=True
for i in range(n):
    if x[i]==INF:
        f&=dfs(i)
# print(x)
yn(f)

Submission status: Accepted

Solution code:
class WeightedUF:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.weight = [0] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def unite(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)

        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

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

n,m=map(int,input().split())
wuf=WeightedUF(n)
for i in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    if wuf.same(l,r):
        if wuf.diff(l,r)!=d:
            print("No")
            exit()
    else:
        wuf.unite(l,r,d)
print("Yes")

Submission status: Accepted

Solution code:
from collections import namedtuple, deque

class Person:
    def __init__(self, id, conn, x):
        self.id = id
        self.conn = conn
        self.x = x

def main():
    with open(0) as f:
        N, M = map(int, f.readline().split())
        info = [tuple(map(int, line.split())) for line in f.readlines()]
    people = [Person(i, conn=[], x=None) for i in range(N)]
    for l, r, d in info:
        people[l-1].conn.append((r-1, d))
        people[r-1].conn.append((l-1, -d))
    
    for person in people:
        if person.x is not None:
            continue
        else:
            person.x = person.id
            #bfs
            reserved = deque([person])
            seen = {person.id}
            while len(reserved) > 0:
                current = reserved.popleft()
                for next_person_id, d in current.conn:
                    if people[next_person_id].x is None:
                        people[next_person_id].x = current.x + d
                    else:
                        if people[next_person_id].x != current.x + d:
                            print('No')
                            return None
                    if next_person_id in seen:
                        continue
                    seen.add(next_person_id)
                    reserved.append(people[next_person_id])
    print('Yes')

main()

Submission status: Accepted

Solution code:
# 重み付きUnionFind
#############################################################
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        # 根への距離を管理
        self.weight = [0] * (n + 1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
#############################################################

# 大小関係が複数与えられるような問題では、重み付きUnionFindが使えることが多い

N, M = map(int, input().split())
wuf = WeightedUnionFind(N)

for _ in range(M):
    l, r, d = map(int, input().split())
    if wuf.same(l, r):
        # lからrへの重みがdか否か
        if wuf.diff(l, r) != d:
            print("No")
            exit()
    else:
        # lからrへの重みはdであるとする
        wuf.union(l, r, d)

print("Yes")

Submission status: Accepted

Solution code:
from collections import deque
import sys
N, M = map(int, input().split())
K = [[] for _ in range(N)]
for i in range(M):
    L, R, D = map(int, input().split())
    K[L-1].append([R-1, D])
    K[R-1].append([L-1, -D])
used = [0]*(N+1)
Num = [10**12]*(N+1)
for i in range(N):
    large = 0
    small = 0
    if used[i] == 0:
        used[i] = 1
        Num[i] = 0
        P = deque([i])
        while(True):
            if len(P) == 0:
                break
            a = P.popleft()
            for s, m in K[a]:
                if Num[s] == 10**12:
                    Num[s] = Num[a] + m
                else:
                    if Num[s] != Num[a]+m:
                        print("No")
                        sys.exit()
                large = max(large, Num[s])
                small = min(small, Num[s])
                if used[s] == 0:
                    used[s] = 1
                    P.append(s)
        if large - small > 10**9:
            print("No")
            sys.exit()
print("Yes")

Submission status: Accepted

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

# 重要な事実としてNの最大値×D_iの最大値はちょうど10^4*10^5 = 10^9 = 座標の幅。
# 「位置関係は全て正しく置けるが、0〜10^9に収まらないのでダメ」という可能性は考慮しなくて良い。
# 辺を通って到達可能か否かで分かれる。→幅優先か深さ優先かUnion-Findだな。
# 迷ったら幅優先で書こう。
# なおエッジを1本ずつ（入力された順に）処理するのはマズい。100個の点からなる塊が2つあって、最後にそれが2つの線で結ばれた場合、無矛盾かどうかどうやって判別するか?

from collections import deque

nei = [[] for _ in range(n)]
for edge in info:
    v0 = edge[0] - 1
    v1 = edge[1] - 1
    nei[v0].append((v1, edge[2]))
    nei[v1].append((v0, -edge[2]))

queue = deque()
visited = [False] * n
pos = [None] * n

for i in range(n):
    if visited[i]:
        continue
    queue.append(i)

    pos[i] = 0  # 相対位置なので、値は何でも良い

    while len(queue) > 0:
        v = queue.popleft()
        visited[v] = True

        for n, diff in nei[v]:
            if pos[n] == None:
                pos[n] = pos[v] + diff
                queue.append(n)

            else:
                # 既に訪問済み→座標が決まっている→整合性チェック
                if pos[n] != pos[v] + diff:
                    print('No')
                    exit()

print('Yes')

Submission status: Accepted

Solution code:
class WeighttedUnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n+1)]
		self.rank = [0] * (n+1)
		#根への距離を管理
		self.weight = [0] * (n+1)

	#検索
	def find(self, x):
		if self.par[x] ==x:
			return x
		else:
			y = self.find(self.par[x])
			#根への重みを追加しながら根まで走査
			self.weight[x] +=self.weight[self.par[x]]
			self.par[x] = y
			return y

	def union(self, x, y, w):
		rx = self.find(x)
		ry = self.find(y)

		#xの木の高さ < yの木の高さ
		if self.rank[rx] < self.rank[ry]:
			self.par[rx] = ry
			self.weight[rx] = w - self.weight[x] + self.weight[y]

		#xの木の高さ>=yの木の高さ
		else:
			self.par[ry] = rx
			self.weight[ry] = -w - self.weight[y] + self.weight[x]
			#木の高さが同じだった場合の処理
			if self.rank[rx] == self.rank[ry]:
				self.rank[rx] +=1
	#同じ集合に属するか
	def same(self, x, y):
		return self.find(x) == self.find(y)
	#xからyへのコスト
	def diff(self, x, y):
		return self.weight[x] - self.weight[y]

N, M = map(int, input().split())
wuf = WeighttedUnionFind(N)

for _ in range(M):
	l, r, d = map(int, input().split())

	if not wuf.same(l, r):
		wuf.union(l, r, d)

	else:
		if wuf.diff(l, r) !=d:
			print("No")
			exit()
print("Yes")