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:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)
from collections import defaultdict, deque
def inpl(): return tuple(map(int, input().split()))

N, M = inpl()
Q = [inpl() for _ in range(M)]
# グループごとにトポロジカルソートをして、最後の方から遡って計算

tree = [[-1, 1]  for _ in range(N+1)] # [next, rank]
  
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px

adj = [[] for _ in range(N+1)]  

for l, r, d in Q:
    if find(l) != find(r):
        unite(l, r)
    adj[l].append([r, d])
    adj[r].append([l, -d])


G = set([find(n) for n in range(1, N+1)])

X = [-1 for _ in range(N+1)]
searched = [False for _ in range(N+1)]
res = True

for g in G:
    X[g] = 0
    Q = deque([g])
    while Q:
        p = Q.popleft()
        searched[p] = True
        for np, d in adj[p]:
            if searched[np]:
                if X[np] != X[p] + d:
                    Q = []
                    res = False
                    break
            else:
                X[np] = X[p] + d
                Q.append(np)
    if not res:
        break

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(300000)


def dfs(x, ls, rs, pos):
    if pos[x] is None:
        pos[x] = 0
    xpos = pos[x]
    
    for r, d in ls.get(x, []):
        if pos[r] is not None:
            if pos[r] - xpos != d:
                return False
        else:
            pos[r] = xpos + d
            if not dfs(r, ls, rs, pos):
                return False
    for l, d in rs.get(x, []):
        if pos[l] is not None:
            if xpos - pos[l] != d:
                return False
        else:
            pos[l] = xpos - d
            if not dfs(l, ls, rs, pos):
                return False
    return True


def main():
    n, m = list(map(int, input().split()))
    pos = [None for _ in range(n + 1)]

    ls = {}
    rs = {}
    for _ in range(m):
        l, r, d = list(map(int, input().split()))
        lsl = ls.get(l, [])
        lsl.append((r, d))
        ls[l] = lsl
        rsr = rs.get(r, [])
        rsr.append((l, d))
        rs[r] = rsr

    for i in range(n):
        if not dfs(i+1, ls, rs, pos):
            print('No')
            return

    pos = list(filter(lambda x: x is not None, pos))
    if len(pos) > 0:
        L, R = min(pos), max(pos)
        if R - L > 1e9:
            print('No')
            return

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,time
sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if time.time() - start > 0.9:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys,time
sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if time.time() - start > 1.5:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys,time
sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        gt = time.time() - start
        if gt > 1.7:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
union = list(range(N + 1))
dist = [0] * (N + 1)

def ascend(anc):
	tmp_d = dist[anc]
	if union[anc] == anc:
		return anc, tmp_d
	else:
		union[anc], d_sum = ascend(union[anc])
		dist[anc] = tmp_d + d_sum
	return union[anc], dist[anc]

def connect(l, r, d):
	l_anc, l_d = ascend(l)
	r_anc, r_d = ascend(r)
	if l_anc != r_anc:
		union[l_anc] = r_anc
		dist[l_anc] = dist[r] + d - dist[l]

def is_union(l, r):
	l_anc, l_d = ascend(l)
	r_anc, r_d = ascend(r) 
	return l_anc == r_anc

def check(l, r, d):
	l_anc, l_d = ascend(l)
	r_anc, r_d = ascend(r)
	return r_d + d == l_d

for i in range(M):
	l, r, d = map(int, input().split())
	if is_union(l, r):
		if not check(l, r, d):
			print("No")
			break
	else:
		connect(l, r, d)
else:
	print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Time Limit Exceeded

Solution code:
#def fun():
import bisect

[N,M]=map(int,raw_input().split())
A=[[] for i in range(N)]
K=[]
#for i in range(1,N+1):
#    A[i]=[]
bignum=-100000000000
C=[bignum for x in range(N+1)]
for i in range(M):
    [L,R,D]=map(int,raw_input().split())
    if L>R:
        [L,R,D]=[R,L,-D]
    A[L].append([R,D])
    #A[R].append([L,-D])
    if L not in K:
        K.append(L)
    #if R not in K:
    #    K.append(R)
#K=A.keys()
K.sort
E=[]
flg=1
while len(K)!=0 or len(E)!=0:
    if len(E)==0:
        k=K.pop(0)
        C[k]=0
    else:
        k=E.pop(0)
    a=A[k]
    for aa in a:
        [n,d]=aa
        if C[n]!=bignum and C[n]!=C[k]+d:
            print "No"
            flg=0
        else:
            C[n]=C[k]+d
        id =min(bisect.bisect_left(K,n),len(K))
        if len(K)!=0 and K[id]==n:
            K=K[:id]+K[id+1:]
            E.append(n)
    if not flg:
        break
if flg:
    print "Yes"

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        gt = time.time() - start
        if gt > 1.7:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [set() for _ in range(n)]
    for l,r,d in a:
        e[l-1].add((r-1,d))
        e[r-1].add((l-1,-d))

    b = [False] * n
    def g(i,c):
        gt = time.time() - start
        if gt > 1.0:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [set() for _ in range(n)]
    for l,r,d in a:
        e[l-1].add((r-1,d))
        e[r-1].add((l-1,-d))

    b = [False] * n
    def g(i,c):
        gt = time.time() - start
        if gt > 1.9:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####

def main():
	N,M = LI()
	dist = [[0 for _ in range(N)] for _ in range(N)]

	f = True
	for m in range(M):
		l,r,d = LI()
		l -= 1; r -= 1

		if r != 0:
			t = dist[l][r-1] + dist[r-1][r]

			if t != 0:
				if t != d:
					f = False
					break

			dist[l][r] = d
			dist[r][l] = d

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



if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [set() for _ in range(n)]
    for l,r,d in a:
        e[l-1].add((r-1,d))
        e[r-1].add((l-1,-d))

    b = [False] * n
    def g(i,c):
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(300000)


def dfs(x, ls, rs, pos):
    xpos = 0 if pos[x] is None else pos[x]
    for r, d in ls.get(x, []):
        if pos[r] is not None:
            if pos[r] - xpos != d:
                return False
        else:
            pos[r] = xpos + d
            if not dfs(r, ls, rs, pos):
                return False
    for l, d in rs.get(x, []):
        if pos[l] is not None:
            if xpos - pos[l] != d:
                return False
        else:
            pos[l] = xpos - d
            if not dfs(l, ls, rs, pos):
                return False
    return True


def main():
    n, m = list(map(int, input().split()))
    pos = [None for _ in range(n + 1)]

    ls = {}
    rs = {}
    for _ in range(m):
        l, r, d = list(map(int, input().split()))
        lsl = ls.get(l, [])
        lsl.append((r, d))
        ls[l] = lsl
        rsr = rs.get(r, [])
        rsr.append((l, d))
        rs[r] = rsr

    for i in range(n):
        if not dfs(i+1, ls, rs, pos):
            print('No')
            return

    pos = list(filter(lambda x: x is not None, pos))
    if len(pos) > 0:
        L, R = min(pos), max(pos)
        if R - L > 1e9:
            print('No')
            return

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if b[i] != False:
            return b[i] == c
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Time Limit Exceeded

Solution code:
MAX = 10**9

def main():
    n, m = map(int, input().split())
    info = []
    for _ in range(m):
        l, r, d = map(int, input().split())
        info.append([l-1, r-1, d])
    info.sort()
    min_x = None
    max_x = None
    x = {}
    while info:
        for l, r, _ in info:
            if l in x:
                p = l
                break
            elif r in x:
                p = r
                break
        else:
            if min_x is not None:
                if max_x - min_x > MAX:
                    print('No')
                    return
            p = info[0][0]
            x = {p: 0}
            max_x = min_x = 0
        rest = []
        for l, r, d in info:
            if l in x:
                pr = x[l] + d
                if r not in x:
                    x[r] = pr
                    max_x = max(max_x, pr)
                    min_x = min(min_x, pr)
                elif x[r] != pr:
                    print('No')
                    return
            elif r in x:
                pl = x[r] - d
                if l not in x:
                    x[l] = pl
                    max_x = max(max_x, pl)
                    min_x = min(min_x, pl)
                elif x[l] != pl:
                    print('No')
                    return
            else:
                rest.append([l, r, d])
        info = rest
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)


def check(i, xs, checked):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if j in checked:
            continue
        xj = xs[j]
        if xj is None:
            xs[j] = xi + d
        elif xi + d != xj:
            return False
        children.add(j)
    checked.add(i)
    for j in children:
        if j in checked:
            continue
        if not check(j, xs, checked):
            return False
    return True


def solve():
    checked = set()
    for i in range(n):
        if i not in checked:
            xs = [None] * n
            xs[i] = 0
            res = check(i, xs, checked)
            if not res:
                return False
            xf = [x for x in xs if x is not None]
            mn, mx = min(xf), max(xf)
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)


def check(i, xs, checked):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if j in checked:
            continue
        xj = xs[j]
        if xj is None:
            xs[j] = xi + d
        elif xi + d != xj:
            return False
        children.add(j)
    checked.add(i)
    for jc in children:
        if not check(jc, xs, checked):
            return False
    return True


def solve():
    checked = set()
    for i in range(n):
        if i not in checked:
            xs = [None] * n
            xs[i] = 0
            res = check(i, xs, checked)
            if not res:
                return False
            xf = [x for x in xs if x is not None]
            mn, mx = min(xf), max(xf)
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')

Submission status: Time Limit Exceeded

Solution code:
MAX = 10**9

def main():
    n, m = map(int, input().split())
    info = []
    for _ in range(m):
        l, r, d = map(int, input().split())
        info.append([l-1, r-1, d])
    info.sort()
    min_x = None
    max_x = None
    x = [None] * n
    while info:
        for l, r, _ in info:
            if x[l] is not None:
                p = l
                break
            elif x[r] is not None:
                p = r
                break
        else:
            if min_x is not None:
                if max_x - min_x > MAX:
                    print('No')
                    return
            x = [None] * n
            p = info[0][0]
            x[p] = 0
            max_x = min_x = 0
        rest = []
        for l, r, d in info:
            if l == p:
                pr = x[l] + d
                if x[r] is None:
                    x[r] = pr
                    max_x = max(max_x, pr)
                    min_x = min(min_x, pr)
                elif x[r] != pr:
                    print('No')
                    return
            elif r == p:
                pl = x[r] - d
                if x[l] is None:
                    x[l] = pl
                    max_x = max(max_x, pl)
                    min_x = min(min_x, pl)
                elif x[l] != pl:
                    print('No')
                    return
            else:
                rest.append([l, r, d])
        info = rest
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)


def check(i, xs):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if j in checked:
            continue
        xj = xs[j]
        if xj is None:
            xs[j] = xi + d
        elif xi + d != xj:
            return False
        children.add(j)
    checked.add(i)
    for jc in children:
        if not check(jc, xs):
            return False
    return True


def solve():
    for i in range(n):
        if i not in checked:
            xs = [None] * n
            xs[i] = 0
            res = check(i, xs)
            if not res:
                return False
            xf = [x for x in xs if x is not None]
            mn, mx = min(xf), max(xf)
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
checked = set()
print('Yes' if solve() else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)


def check(i, xs):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if j in checked:
            continue
        xj = xs[j]
        if xj is None:
            xs[j] = xi + d
        elif xi + d != xj:
            return False
        children.add(j)
    checked.add(i)
    for jc in children:
        if not check(jc, xs):
            return False
    return True


def solve():
    for i in range(n):
        if i not in checked:
            xs = [None] * n
            xs[i] = 0
            res = check(i, xs)
            if not res:
                return False
            xf = list(filter(lambda x: x is not None, xs))
            mn, mx = min(xf), max(xf)
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
checked = set()
print('Yes' if solve() else 'No')

Submission status: Time Limit Exceeded

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

from collections import defaultdict
E = defaultdict(list)

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

unvisited = set(range(N))
locations = [None]*N
while unvisited:
  s = next(iter(unvisited))
  locations[s] = 0
  stack = [s]

  while stack:
    v = stack.pop()
    unvisited.discard(v)
    p = locations[v]

    for u,d in E[v]:
      if locations[u] is None:
        locations[u] = p+d
        stack.append(u)
      elif locations[u] != p+d:
        print('No')
        exit()

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if b[i] != False:
            if c == False:
                return True
            return b[i] == c
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())