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

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

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:
        print("No")
        exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
import numpy as np
print('Yes')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = []
R = []
D = []
for i in range(M):
    tmp = input().split()
    L.append(int(tmp[0]))
    R.append(int(tmp[1]))
    D.append(int(tmp[2]))

pos = {}
ans = "Yes"

for i in range(N):
    pos[i + 1] = 0

for i in range(M):
    if(L[i] < R[i]):
        l = L[i]
        r = R[i]
    else:
        l = R[i]
        r = L[i]
    d = D[i]
    if(pos[r] == 0):
        pos[r] = pos[l] + d
        for j in range(N-r):
            pos[r+1+j] += pos[r]
    else:
        if(pos[l] + d != pos[r]):
            ans = "No"
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# coding=utf-8

import sys

n, m = map(int, sys.stdin.readline().strip().split(" "))
lrd = [list(map(int, l.strip().split(" "))) for l in sys.stdin.readlines()]
lrd = sorted(lrd, key=lambda x: x[0])
hyp = [0 for _ in range(n + 1)]
mark = [0 for _ in range(n + 1)]
flag = True
for _l, _r, _d in lrd:
    if mark[_l] == mark[_r] == 0:
        hyp[_r] = hyp[_l] + _d
        mark[_r] = mark[_l] = 1
    elif mark[_l] == 0:
        hyp[_l] = hyp[_r] - _d
        mark[_l] = 1
    elif mark[_r] == 0:
        hyp[_r] = hyp[_l] + _d
        mark[_r] = 1
    else:
        if hyp[_r] - hyp[_l] != _d:
            flag = False
            break
if flag:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
N, M = map(int, input().split())
x = [-1] * N
ans = True
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if x[R] == -1:
        if x[L] == -1:
            x[L] = 0
        x[R] = x[L] + D
    elif x[L] == -1:
        x[L] = x[R] - D
    else:
        if x[R] - x[L] != D:
            ans = False
m = min(x)
x = map(lambda y: y - m, x)
print(('No', 'Yes')[ans and max(x) <= 10 ** 9])

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split(' '))
X=['p']*n
L=[]
R=[]
D=[]
i=0
while i < m:
    l,r,d = map(int,input().split(' '))
    L.append(l)
    R.append(r)
    D.append(d)
    if X[l-1]=='p' and X[r-1]=='p':
        X[l-1]=0
        X[r-1]=d
    elif X[l-1]=='p':
        X[l-1]=X[r-1]-d
    else:
        X[r-1]=X[l-1]+d
    i += 1
j=0
f=0
while j<m and f==0:
    if X[R[j]-1]-X[L[j]-1] != D[j]:
        f=1
        break
    j += 1
k=0
while k<n:
    if X[k]=='p':
        X[k] = 0
    k+=1
if f==0 and abs(min(X) - max(X)) > 1000000000:
    f=1
if f == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
k = [None] * (n+1)
ans = 'Yes'
for i in range(m):
    l,r,d = map(int,input().split())
    if i == 0: 
        k[l] = 0
        k[r] = d
    else:
        if k[l] is None and k[r] is None:
            k[l] = 0
            k[r] = d
        elif k[l] is not None and k[r] is None:
            k[r] = k[l] + d
        elif k[l] is None and k[r] is not None:
            k[l] = k[r] + d
    if k[r] - k[l] != d:
        ans = 'No'
        break
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
f = lambda :list(map(int,input().split()))
N,M = f()
L,R,D = [],[],[]
posit = [0]*N
changed = [False]*N
flag = False

if M <= 1:
    print("Yes")
    sys.exit()


for i in range(M):
    l,r,d = f()
    L.append(l)
    R.append(r)
    D.append(d)

pivot = L[0]

for i in range(M):
    l, r, d = L[i]-1,R[i]-1,D[i]
    if r == pivot:
        if changed[l] and posit[r] - d != posit[l]:
            flag = True
            break
        else:
            posit[l] = posit[r] - d
    else:
        if changed[r] and posit[l] + d != posit[r]:
            flag = True
            break
        else:
            posit[r] = posit[l] + d
            changed[r] = True


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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":  str(l),
    "right": str(r),
    "dist":  d
  })

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

# 各人の位置(不定の場合は-1)
locations = defaultdict(lambda: -1)

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

  # 左の人物だけが初登場なら，rightの人物の位置から見てdist分左におく
  if locations[info["left"]] == -1 and locations[info["right"]] != -1:
    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 key in locations.keys():
        locations[key] += exceeded_dist

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

  # 右の人物だけが初登場なら，leftの人物から見てdist分右におく
  if locations[info["left"]] != -1 and locations[info["right"]] == -1:
    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 key in locations.keys():
        locations[key] -= exceeded_dist

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

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

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

Submission status: Wrong Answer

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

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

print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
f = lambda :list(map(int,input().split()))
N,M = f()
L,R,D = [],[],[]
posit = [0]*N
changed = [False]*N
flag = False

if M <= 1:
    print("Yes")
    sys.exit()


for i in range(M):
    l,r,d = f()
    L.append(l)
    R.append(r)
    D.append(d)

pivot = L[0]

for i in range(M):
    l, r, d = L[i]-1,R[i]-1,D[i]
    print(posit)
    if r == pivot:
        if changed[l] and posit[r] - d != posit[l]:
            flag = True
            break
        else:
            posit[l] = posit[r] - d
    else:
        if changed[r] and posit[l] + d != posit[r]:
            flag = True
            break
        else:
            posit[r] = posit[l] + d
            changed[r] = True


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

Submission status: Wrong Answer

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

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]]>=0 and nl[c[1]]>=0:
        if nl[c[1]]-nl[c[0]]==c[2]:
            pass
        else:
            print("No")
            exit()
    else:
        print("No")
        exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
N, M = map(int, input().split())
x = [-1] * N
ans = True
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if x[R] == -1:
        if x[L] == -1:
            x[L] = 0
        x[R] = x[L] + D
    elif x[L] == -1:
        x[L] = x[R] - D
    else:
        if x[R] - x[L] != D:
            ans = False
print(('No', 'Yes')[ans])

Submission status: Wrong Answer

Solution code:
#-*- coding:utf-8 -*-
import sys

N, M = map(int, raw_input().split())
arr = []
for i in range(M):
    arr.append(map(int, raw_input().split()))

for i in range(M):
    l = arr[i][0]
    r = arr[i][1]
    d = r - l
    if d != arr[i][2]:
        print "No"
        sys.exit()

print "Yes"

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = []
R = []
D = []
for i in range(M):
    tmp = input().split()
    L.append(int(tmp[0]))
    R.append(int(tmp[1]))
    D.append(int(tmp[2]))

pos = {}
ans = "Yes"

for i in range(N):
    pos[i + 1] = 0

for i in range(M):
    if(L[i] < R[i]):
        l = L[i]
        r = R[i]
    else:
        l = R[i]
        r = L[i]
    d = D[i]
    if(pos[r] == 0):
        pos[r] = pos[l] + d
    else:
        if(pos[l] + d != pos[r]):
            ans = "No"

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
N, M = map(int, input().split())
x = [-1] * N
ans = True
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if x[R] == -1:
        if x[L] == -1:
            x[L] = 0
        x[R] = x[L] + D
    else:
        if x[R] - x[L] != D:
            ans = False
print(('No', 'Yes')[ans])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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,
    "right": r,
    "dist":  d
  })

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

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

for info in info_list:
  # 左右の人物が共に初登場なら，とりあえずleftを0において，rightを距離の分だけ離す
  # 条件から外れることはない
  if locations[info["left"]] == -1 and locations[info["right"]] == -1:
    locations[info["left"]] = 0
    locations[info["right"]] = info["dist"]
    continue

  # 左の人物だけが初登場なら，rightの人物の位置から見てdist分左におく
  # 条件から外れることはない
  if locations[info["left"]] == -1:
    locations[info["left"]] = locations[info["right"]] - info["dist"]
    continue

  # 右の人物だけが初登場なら，leftの人物から見てdist分右におく
  # 条件から外れることはない
  if locations[info["right"]] == -1:
    locations[info["right"]] = locations[info["left"]] + info["dist"]
    continue

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

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

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split(' '))
X=[0]*n
L=[]
R=[]
D=[]
i=0
while i < m:
    l,r,d = map(int,input().split(' '))
    X[r-1] = X[l-1] + d
    L.append(l)
    R.append(r)
    D.append(d)
    i += 1
j=0
f=0
while j<m and f==0:
    if X[R[j]-1]-X[L[j]-1] != D[j]:
        f=1
        break
    j += 1
if abs(min(X) - max(X)) > 1000000000:
    f=1
if f == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra(N,start, goal,E):
    """最短距離,経路を返すプログラム"""
    dist = [float('inf')] * N          #dist[i]:始点からの距離
    path = [tuple() for n in range(N)] #path[i]:(start,...,i)までの経路をカンマで区切ったもの
    dist[start] = 0
    path[start] = (start, )            
    pq = [(0, path[start])]

    while pq:
        di, pathi = heapq.heappop(pq)
        v = pathi[-1]
        if v == goal:
            return di

        #辺を全部見る
        for vertex, weight in E[v].items():
            new_di = di + weight
            if (new_di < dist[vertex]) or (new_di == dist[vertex] and pathi + (vertex, ) < path[vertex]):
                dist[vertex] = new_di
                path[vertex] = pathi + (vertex, )
                heapq.heappush(pq, (new_di, path[vertex]))

    return -1

class UnionFind():
    def __init__(self, n):
        self.table = [i for i in range(n)]
        self.rank = [1 for _ in range(n)]

    def unite(self, x, y):
        # x,yの根を格納する 
        x = self.find(x)
        y = self.find(y)

        #同一グラフ内だった場合
        if x == y:
            return False

        if self.rank[x] > self.rank[y]:
            self.table[y] = x
        else:
            self.table[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1


    def find(self, x):
        """ xの根の値を返すメソッド """
        #xが根である時
        if self.table[x] == x:
            return x
        #xが根でない ==> 根へたどる&根へつけかえる
        self.table[x] = self.find(self.table[x])
        #根の値を返す
        return self.table[x]

    def SameGragh(self,x,y):
        """二つの値が同一グラフ内だった場合:True,違う場合:False"""
        if self.find(x) == self.find(y):
            return True
        else:
            return False

N,M = map(int,input().split(" "))
E = [dict() for i in range(N)]
tree = UnionFind(N)
for i in range(M):
    L,R,D = map(int,input().split(" "))
    if tree.SameGragh(L-1,R-1):
        di = dijkstra(N,L-1,R-1,E)
        if di != D:
            print("No")
            exit(0)

    else:
        E[L-1][R-1] = D
        tree.unite(L-1,R-1)

print("Yes")

Submission status: Time Limit Exceeded

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

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

print('Yes', flush=True)

Submission status: Time Limit Exceeded

Solution code:
# 解説みたよ
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
l, r, d = [0] * m, [0] * m, [0] * m
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1
    es[l[i]].append((r[i], d[i]))
    es[r[i]].append((l[i], -d[i]))
INF = 1000000000000
value = [INF] * n


def dfs(v):
    for i, di in es[v]:
        if value[i] == INF:
            value[i] = value[v] + di
            dfs(i)


for i in range(n):
    if value[i] == INF:
        value[i] = 0
        dfs(i)

for i in range(m):
    if value[r[i]] - value[l[i]] != d[i]:
        print("No")
        exit()
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
# 解説みたよ
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
l, r, d = [0] * m, [0] * m, [0] * m
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1
    es[l[i]].append((r[i], d[i]))
    es[r[i]].append((l[i], -d[i]))
INF = 1000000000000
value = [INF] * n


def dfs(v):
    for i, di in es[v]:
        if value[i] == INF:
            value[i] = value[v] + di
            dfs(i)


for i in range(n):
    if value[i] == INF:
        value[i] = 0
        dfs(i)

for i, j, k in zip(l, r, d):
    if value[j] - value[i] != k:
        print("No")
        exit()
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
# 解説みたよ
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
l, r, d = [0] * m, [0] * m, [0] * m
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1
    es[l[i]].append((r[i], d[i]))
    es[r[i]].append((l[i], -d[i]))
INF = 1000000000000
value = [INF] * n


def dfs(v):
    for i, d in es[v]:
        if value[i] == INF:
            value[i] = value[v] + d
            dfs(i)


for i in range(n):
    if value[i] == INF:
        value[i] = 0
        dfs(i)

for i, j, k in zip(l, r, d):
    if value[j] - value[i] != k:
        print("No")
        exit()
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        '''
        注意：0-idx
        '''
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

Person, Info = map(int,input().split())
# left_info[i] := 人iについての情報[r,d]のリスト
left_info = [[] for _ in range(Person)]
LR_done = defaultdict(int)

uf = UnionFind(Person)
for i in range(Info):
    l,r,d = map(int,input().split())
    l,r = l-1,r-1
    left_info[l].append([r,d])
    left_info[r].append([l,-d])
    uf.union(l,r)

def is_valid(root):
    '''
    rootのグループ内で矛盾がないか調べる
    '''
    q = deque()
    # 初期状態
    for r,d in left_info[root]:
        q.append([root,r,d])
        LR_done[(root,r)] = 1
        LR_done[(r,root)] = 1
    person_point = [0] * Person
    person_once = [0] * Person
    person_once[root] = 1
    person_point[root] = 0

    # 常にlからrに
    while q:
        l,r,d = q.pop()
        if not person_once[r]:
            person_point[r] = person_point[l] + d
            person_once[r] = 1
        else:
            if person_point[r] == person_point[l] + d:
                pass
            else:
                return False
        # rからのedgeをqに追加
        for new_r,new_d in left_info[r]:
            if not (LR_done[(r,new_r)] or LR_done[(new_r,r)]):
                q.append([r,new_r,new_d])
                LR_done[(r,new_r)] = 1
                LR_done[(r,new_r)] = 1
    return True

res = 'Yes'
for root in uf.roots():
    if not is_valid(root):
        res = 'No'
        break
print(res)

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
    l, r, d = map(int, input().split())
    graph[l].append([r, d])
    graph[r].append([l, -d])
flags = [False for i in range(n + 1)]
place = [0 for i in range(n + 1)]

num = 0
flag = True
while num <= n:
    if flag == False:
        break
    if flags[num] == True:
        num += 1
        continue
    if graph[num] == []:
        flags[num] = True
        num += 1
        continue
    queue = collections.deque([num])
    while queue:
        if flag == False:
            break
        test = queue.popleft()
        flags[test] = True
        for i in graph[test]:
            if flags[i[0]] == True:
                if place[i[0]] - place[test] != i[1]:
                    flag = False
                    break
            else:
                place[i[0]] = place[test] + i[1]
                queue.append(i[0])
    else:
        num += 1
if flag == True:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import collections

n, m = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
    l, r, d = map(int, input().split())
    graph[l].append([r, d])
    graph[r].append([l, -d])
flags = [False for i in range(n + 1)]
place = [None for i in range(n + 1)]
num = 0
flag = True
while num <= n:
    if flag == False:
        break
    if flags[num] == True:
        num += 1
        continue
    if graph[num] == []:
        place[num] = 0
        flags[num] = True
        num += 1
        continue
    place[num] = 0
    queue = collections.deque([num])
    while queue:
        test = queue.popleft()
        flags[test] = True
        for i in graph[test]:
            if flags[i[0]] == True:
                if place[i[0]] - place[test] != i[1]:
                    flag = False
                    break
            else:
                place[i[0]] = place[test] + i[1]
                queue.append(i[0])
    else:
        num += 1
if flag == True:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(300000)

N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  l,r,d = map(int, input().split())
  l,r = l-1,r-1
  E[l].append((r,d))
  E[r].append((l,-d)) 
  
#for e in E:
#  print(e)
  
# dfs
visited = [False] * N

INF = 10**16
A = [ INF ] * N

def dfs(now, prev, num):
  visited[now] = True
  if A[now] == INF:
    A[now] = num
  else:
    pass
  for nxt, dis in E[now]:
    if nxt == prev:
      continue
    if A[nxt] < INF and A[nxt] != num + dis:
      # ある点において2通りのnum設定の仕方がある
      print("No")
      exit(0)
    if visited[nxt]:
      continue
    dfs(nxt, now, num + dis)
  return 

for i in range(N):
  if visited[i]:
    continue
  dfs(i,-1,0)
  
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heapify,heappop,heappush,heapreplace

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  n,m,*lrd=map(int,read().split())
  hp=[]
  for l,r,d in zip(*[iter(lrd)]*3):
    if l>r:
      hp.append((r,l,-d))
    else:
      hp.append((l,r,d))
  heapify(hp)
  if not hp:
    print('Yes')
    return
  while hp:
    ce=heappop(hp)
    while hp:
      ne=hp[0]
      if ce[0]==ne[0]:
        if ce[1]==ne[1]:
          if ce[2]!=ne[2]:
            print('No')
            return
          else:
            heappop(hp)
        else:
          heapreplace(hp,(ce[1],ne[1],ne[2]-ce[2]))
      else:
        break      
  print('Yes')

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heapify,heappop,heappush,heapreplace

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  n,m,*lrd=map(int,read().split())
  hp=[]
  heapify(hp)
  for l,r,d in zip(*[iter(lrd)]*3):
    if l>r:
      heappush(hp,(r,l,-d))
    else:
      heappush(hp,(l,r,d))
  if len(hp)<2:
    print('Yes')
    return
  while hp:
    ce=heappop(hp)
    while hp:
      ne=hp[0]
      if ce[0]==ne[0]:
        if ce[1]==ne[1]:
          if ce[2]!=ne[2]:
            print('No')
            return
          else:
            heappop(hp)
        else:
          heapreplace(hp,(ce[1],ne[1],ne[2]-ce[2]))
      else:
        break      
  print('Yes')

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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 dfs(u,x):
  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:
      dfs(v,c[u]+d)

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

Submission status: Time Limit Exceeded

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 dfs(u,x):
  if c[u] == INF:
    c[u] = x
  else:
    if c[u] != x:
      print('No')
      exit()
  for v,d in e[u]:
    if c[v] != INF and c[v] == c[u]+d:
      continue
    dfs(v,c[u]+d)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *LRD = map(int, read().split())

    G = [[] for _ in range(N)]
    for l, r, d in zip(*[iter(LRD)] * 3):
        G[l - 1].append((r - 1, d))
        G[r - 1].append((l - 1, -d))

    seen = [False] * N
    for i in range(N):
        if seen[i]:
            continue

        dist = [-1] * N
        dist[i] = 0
        queue = deque([i])
        while queue:
            v = queue.popleft()
            for nv, d in G[v]:
                if seen[nv]:
                    if dist[nv] != dist[v] + d:
                        print('No')
                        return
                else:
                    dist[nv] = dist[v] + d
                    seen[nv] = True
                    queue.append(nv)

    print('Yes')
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

edges = [[] for _ in range(N)]
for _ in range(M):
    l, r, d = map(int, sys.stdin.readline().split())
    edges[l-1].append((r-1, d))
    edges[r-1].append((l-1, -d))

visited = {}
# その人へのパスが複数あり、距離が異なる場合は矛盾
for i in range(N):
    if i in visited:
        continue

    # 連結グラフごとに相対的な距離を決定
    dist = [0 for _ in range(N)]
    q = deque([(i, 0)])
    while q:
        l, c = q.popleft()
        if l in visited:
            if visited[l] != c:
                print("No")
                sys.exit()
            continue
        
        visited[l] = c
        dist[l] = c

        for r, nd in edges[l]:
            q.append((r, c+nd))
    # print(dist)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**6)
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*N]
for _ in [0]*M:
    a, b, d = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append((b, d))
    G[b].append((a, -d))

X = [None]*N

def dfs(i, x=0):
    for j, d in G[i]:
        if X[j] is None:
            X[j] = x+d
            dfs(j, x+d)
        elif X[j] != x+d:
            print('No')
            exit()

for i in range(N):
    if X[i] is not None:
        continue
    X[i] = 0
    dfs(i)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**6)
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*N]

for _ in [0]*M:
    a, b, d = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append((b, d))
    G[b].append((a, -d))

X = [None]*N

def dfs(i, x=0):
    X[i] = x
    for j, d in G[i]:
        if X[j] is not None:
            if X[j] != x+d:
                print('No')
                exit()
            else:
                continue
        dfs(j, x+d)


for i in range(N):
    if X[i] is not None:
        continue
    dfs(i)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*N]

for _ in [0]*M:
    a, b, d = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append((b, d))
    G[b].append((a, -d))

visited = [False]*N
X = [None]*N


def isok(i, x=0):
    visited[i] = True
    X[i] = x

    for j, d in G[i]:
        if X[j] is not None and X[j] != x+d:
            return False
        elif visited[j]:
            continue
        if not isok(j, x+d):
            return False
    return True


for i in range(N):
    if visited[i]:
        continue
    if not isok(i):
        print('No')
        break
else:
    print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    graph[l-1].append((r-1, d))
    graph[r-1].append((l-1, -d))
seen = [False]*n
dist = [None]*n
for i in range(n):
    if seen[i]:
        continue
    q = deque([i])
    dist[i] = 0
    while q:
        node = q.popleft()
        seen[node] = True
        for c_node, d in graph[node]:
            if dist[c_node] is None:
                dist[c_node] = dist[node] + d
            elif dist[c_node] != dist[node] + d:
                print('No')
                exit(0)
            if not seen[c_node]:
                q.append(c_node)
print('Yes')