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: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index):
        if self.parent[index] == index:  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2):  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2:  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2]:
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else:
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2]:
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2):
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index):
        return self.size[self.root(index)]

    def getComponent(self):
        return self.component

N, M = map(int, input().split())
INF = 10**18
tree = UnionFind(N)

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, d = map(int, input().split())
    fr -= 1
    to -= 1
    edges[to].append((fr, d))
    edges[fr].append((to, -d))
    tree.union(fr, to)

minDist = [INF] * N
for start in range(N):
    if tree.root(start) != start:
        continue
    st = [(start, 0)]
    while st:
        now, dist = st.pop()

        if minDist[now] == dist:
            continue

        if minDist[now] != INF and minDist[now] != dist:
            print('No')
            exit()
        minDist[now] = dist

        for to, d in edges[now]:
            if minDist[to] == d + dist:
                continue
            st.append((to, dist + d))

print('Yes')

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    L,R,D = map(int, input().split())
    G[L-1].append((R-1, D))
    G[R-1].append((L-1, -D))

dist = [0] * N
visited = [False] * N

def dfs(v:int):
    """ 矛盾がある -> True """
    stack = [v]
    dist[v] = 0
    visited[v] = True

    while stack:
        v = stack.pop()
        d = dist[v]
        for to, cost in G[v]:
            if visited[to]:
                if dist[to] != d + cost:
                    return True
            else:
                visited[to] = True
                dist[to] = d + cost
                stack.append(to)
    
    return False

flag = True
for v in range(N):
    if not visited[v]:
        if dfs(v):
            flag = False
            break

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())

    par = [i for i in range(N)]
    rank = [1]*N
    weight = [0]*N

    def find_root(x):
        if par[x] == x:
            return x
        else:
            r = find_root(par[x])
            weight[x] += weight[par[x]]
            par[x] = r
            return par[x]

    def get_weight(x):
        find_root(x)
        return weight[x]

    def get_diff(x, y):
        return get_weight(y) - get_weight(x)

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y, w):
        w += get_weight(x)
        w -= get_weight(y)
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
            w = -w
        rank[x] += rank[y]
        par[y] = x
        weight[y] = w

    def size(x):
        # 連結成分のサイズを返す
        return rank[find_root(x)]

    for i in range(M):
        le, ri, d = (int(i) for i in input().split())
        le -= 1
        ri -= 1
        if is_same_group(le, ri):
            diff = get_diff(le, ri)
            if diff != d:
                return print("No")
        else:
            unite(le, ri, d)
    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n, m = map(int, input().split())

g = [[] for _ in range(n)]
edge = [{} for _ in range(n)]

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

s = []
visit = [10**18]*n
for i in range(n):
    if visit[i] != 10**18:
        continue
    s.append(i)
    visit[i] = 0
    while s:
        v = s.pop()
        for u in g[v]:
            if visit[u] != 10**18:
                if visit[u] != visit[v]+edge[v][u]:
                    print('No')
                    exit()
            else:
                visit[u] = visit[v]+edge[v][u]
                s.append(u)
else:
    print('Yes')

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
info = [[] for _ in range(n)]
visited = [0] * n
dist = [0] * n
ans = 'Yes'
for i in range(m):
    l, r, D = map(int, input().split())
    info[l-1].append([r-1, D])
    info[r-1].append([l-1, -D])

for i in range(n):
    if visited[i]:
        continue
    q = deque()
    q.append(i)
    while q:
        p = q.pop()
        for x, d in info[p]:
            if visited[x] == 0:
                visited[x] = 1
                dist[x] = dist[p] + d
                q.append(x)
            elif dist[x] != dist[p] + d:
                ans = 'No'

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        Edge[l-1].append((r-1, d))
        Edge[r-1].append((l-1, -1 * d))
    Dist = [10 ** 20] * N
    possible = True
    for i in range(N):
        if Dist[i] == 10 ** 20:
            q = deque()
            q.append((i, 0))
            while q:
                nn, nd = q.popleft()
                if Dist[nn] == 10 ** 20:
                    Dist[nn] = nd
                    for ne, add in Edge[nn]: q.append((ne, nd + add))
                else:
                    if Dist[nn] == nd: continue
                    else:
                        possible = False
                        break
            if not possible:
                print("No")
                break
    else: print("Yes")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    #LRD=[tuple(map(int, input().split())) for _ in range(M)]
    G = [[] for _ in range(N)]
    ny = [0]*N #入次数
    for _ in range(M):
        l,r,d=map(int, input().split())
        l,r=l-1,r-1
        G[l].append((r,d))
        ny[r]+=1

    S=[(i,0) for i in range(N) if ny[i]==0]
    D=[-1]*N
    while S:
        v,dv = S.pop()
        if D[v] >= 0:
            if D[v] != dv:
                print('No')
                exit()
            continue
        D[v] = dv
        for to,d in G[v]:
            S.append((to,dv+d))
    if D.count(-1) > 0:
        print('No')
    else:
        print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

sys.setrecursionlimit(10**9)

def dfs(l,d):
    loc[l]=d
    for n_l,n_d in way[l]:
        if loc[n_l]==10**9:
            dfs(n_l,d+n_d)
        elif loc[n_l]!=d+n_d:
            print("No")
            exit()

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

way=[[] for i in range(N)]
loc=[10**9]*N

for _ in range(M):
    L,R,D=map(int,input().split())
    way[L-1].append([R-1,D])
    way[R-1].append([L-1,-D])

for i in range(N):
    if loc[i]==10**9:
        dfs(i,0)

print("Yes")

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc087/tasks/arc090_b
# ノードL→RへのコストはDであるとすれば、有向グラフと見なせる
# 任意のノードからbfsをして座標をメモしていけば良い。
# 探索済みのノードに到達したときに座標があっているかチェック、あっていればそれ以上探索する必要はない。

# 連結していないグラフがあるかもしれない。(だけど連結していないグラフはお互いに独立)
# 0以上10**9以下っていう制約なのでそこでWAを出されるかと思ったがそんなことなかった


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


from collections import defaultdict, deque

N, M = read_ints()
graph = defaultdict(lambda: [])  # 有向グラフ、隣接リスト形式
for _ in range(M):  # データ読み込み
    l, r, d = read_ints()
    l -= 1
    r -= 1
    graph[l].append((r, d))
    graph[r].append((l, -d))

# bfs
X = [None] * N  # visitedも兼ねる


def bfs(u):  # スタートするノードを入れる
    que = deque([(u, 0)])  # (今のノード,今の座標)
    X[u] = 0
    while que:
        u, x = que.popleft()
        # print(u, x)
        for nu, add in graph[u]:
            nx = x + add
            if X[nu] == nx:
                continue
            # 次の探索
            if X[nu] is not None and X[nu] != nx:
                print('No')
                exit()
            X[nu] = nx
            que.append((nu, nx))


for u in range(N):
    if X[u] is None:
        bfs(u)
print('Yes')

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc087/tasks/arc090_b
# ノードL→RへのコストはDであるとすれば、有向グラフと見なせる
# 任意のノードからbfsをしてメモしていけば良い
# 連結していないグラフがあるかもしれない。(だけど連結していないグラフはお互いに独立)


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


from collections import defaultdict, deque

N, M = read_ints()
graph = defaultdict(lambda: [])  # 有向グラフ、隣接リスト形式
for _ in range(M):  # データ読み込み
    l, r, d = read_ints()
    l -= 1
    r -= 1
    graph[l].append((r, d))
    graph[r].append((l, -d))

# bfs
X = [None] * N  # visitedも兼ねる


def bfs(u):  # スタートするノードを入れる
    que = deque([(u, 0)])  # (今のノード,今の座標)
    X[u] = 0
    while que:
        u, x = que.popleft()
        # print(u, x)
        for nu, add in graph[u]:
            nx = x + add
            if X[nu] == nx:
                continue
            # 次の探索
            if X[nu] is not None and X[nu] != nx:
                print('No')
                exit()
            X[nu] = nx
            que.append((nu, nx))


for u in range(N):
    if X[u] is None:
        bfs(u)
print('Yes')

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**5)
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        self.weight = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            r = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = r
            return r
    def GetWeight(self, x):
        self.Find_Root(x)
        return self.weight[x]
    def Unite(self, x, y, w):
        w += self.GetWeight(x)
        w -= self.GetWeight(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False
        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        self.root[y] = x
        self.weight[y] = w
        return True
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    def Diff(self, x, y):
        return self.GetWeight(y) - self.GetWeight(x)

n, m = map(int, input().split())
if m == 0:
    print('Yes')
    exit()
lrd = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for l, r, d in lrd:
    if uf.isSameGroup(l, r)==False:
        uf.Unite(l, r, d)
    else:
        if uf.Diff(l, r) != d:
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
#PyPy遅え
import sys
sys.setrecursionlimit(400000000)
inf=1000000000000000000
n,m=map(int,input().split())
x=[inf]*n
#まだ訪問してなければTrue
check=[True]*n
#どこと関係があるかを記録する(maybe right)
lrd=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    lrd[l].append((r,d))
    lrd[r].append((l,-d))
#wrong thought
#どっちも決まってない場合の処理
#決まってるとこからやれば良い
#ソートして順番に決めておく

#記録した関係から辿っていく
#まず初めのやつ決定
#非連結な場合を忘れていた


def bfs(z):
    #globalくらいちゃんとしろ
    global lrd,check,x
    for i in range(len(lrd[z])):
        k=lrd[z][i]
        if check[k[0]]:
            x[k[0]]=x[z]+k[1]
            check[k[0]]=False
            bfs(k[0])
        else:
            if x[k[0]]!=x[z]+k[1]:
                print("No")
                sys.exit()
st=0
while any(check):
    for i in range(st,n):
        if len(lrd[i])!=0 and check[i]:
            st=i
            break
        else:
            check[i]=False
    else:
        break
    x[st]=0
    check[st]=False
    bfs(st)
print("Yes")

Submission status: Accepted

Solution code:
#PyPy遅え
import sys
sys.setrecursionlimit(100000000)
inf=1000000000000000000
n,m=map(int,input().split())
x=[inf]*n
#まだ訪問してなければTrue
check=[True]*n
#どこと関係があるかを記録する(maybe right)
lrd=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    lrd[l].append((r,d))
    lrd[r].append((l,-d))
#wrong thought
#どっちも決まってない場合の処理
#決まってるとこからやれば良い
#ソートして順番に決めておく

#記録した関係から辿っていく
#まず初めのやつ
st=-1
for i in range(n):
    if len(lrd[i])>=1:
        st=i
        break

def bfs(z):
    #globalくらいちゃんとしろ
    global lrd,check,x
    for i in range(len(lrd[z])):
        k=lrd[z][i]
        if check[k[0]]:
            x[k[0]]=x[z]+k[1]
            check[k[0]]=False
            bfs(k[0])

st=0
while any(check):
    for i in range(st,n):
        if len(lrd[i])!=0 and check[i]:
            st=i
            break
        else:
            check[i]=False
    else:
        break
    x[st]=0
    check[st]=False
    bfs(st)

for i in range(n):
    l=len(lrd[i])
    for j in range(l):
        k=lrd[i][j]
        if x[k[0]]!=x[i]+k[1]:
            print("No")
            sys.exit()
print("Yes")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
N, M = map(int, input().split(' '))
graph = [[] for _ in range(N)]
for i in range(M):
    l, r, d = map(int, input().split(' '))
    l -= 1
    r -= 1
    graph[l].append((r, d))
    graph[r].append((l, -d))

dsts = [float('inf') for _ in range(N)]

for n in range(N):
    if dsts[n] != float('inf'):
        continue

    buf = deque()
    buf.append(n)
    dsts[n] = 0
    while buf:
        src = buf.popleft()
        for dst, d, in graph[src]:
            next_d = dsts[src] + d

            if dsts[dst] == float('inf'):
                dsts[dst] = next_d
                buf.append(dst)

            elif dsts[dst]  != next_d:
                # print(dsts)
                # print(dst, src, dsts[dst], dsts[src], d, next_d)
                print("No")
                exit()

print("Yes")

Submission status: Accepted

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [-1]*(n+1)
        self.weight = [0]*(n+1)
    
    """ xの根を求める"""
    def Find_Root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            y = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = y
            return y
    
    """ 木の合併 """
    def Union(self, x, y, w):
        rx = self.Find_Root(x)
        ry = self.Find_Root(y)
        
        if self.rnk[rx] < self.rnk[ry]:
            self.root[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        
        else:
            self.root[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rnk[rx] == self.rnk[ry]:
                self.rnk[rx] += 1
    
    """ xとyが同じ木に所属するかの判定 """
    def IsSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    """ x,yのノード重みの取得 """
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
    
    """ xが属する木のサイズ(集合の個数)を取得 """
    def Size(self, x):
        return -self.root[self.Find_Root(x)]
n,m = map(int,input().split())
wuf = WeightedUnionFind(n)
flg = True
for _ in range(m):
    l,r,d = map(int,input().split())
    if not wuf.IsSameGroup(l,r):
        wuf.Union(l,r,d)
    else:
        if wuf.diff(l,r)!=d:
            flg = False
            break
print('Yes' if flg else 'No')

Submission status: Accepted

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


def dfs(p):
    result = True
    for np, D in edge[p]:
        if pos[np] is None:
            pos[np] = pos[p] + D
            result &= dfs(np)
        else:
            if pos[p] + D != pos[np]:
                result &= False
    return result


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for q in sys.stdin.readlines():
    L, R, D = map(int, q.split())
    L -= 1; R -= 1
    edge[L].append((R, D))
    edge[R].append((L, -D))

pos = [None] * N
result = True
for i in range(N):
    if pos[i] is None:
        pos[i] = 0
        result &= dfs(i)

ans = 'Yes' if result else 'No'
print(ans)

Submission status: Accepted

Solution code:
import sys


class UnionFind():
    def __init__(self, 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):
        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


class WeightedUnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
        self.par_weight = [0] * n

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

    def union(self, x, y, w):
        w = w + self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            self.par_weight[x] = -w
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            self.par_weight[y] = w

    def weight(self, x):
        if self.parents[x] < 0:
            return 0
        else:
            return self.par_weight[x] + self.weight(self.parents[x])

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            raise Exception('"{}" belongs to a different tree from "{}"'.format(x, y))
        return self.weight(y) - self.weight(x)


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

ans = 'No'
for q in sys.stdin.readlines():
    L, R, D = map(int, q.split())
    L -= 1; R -= 1

    if uf.find(L) == uf.find(R):
        if uf.diff(L, R) != D:
            break
    else:
        uf.union(L, R, D)
else:
    ans = 'Yes'

print(ans)

Submission status: Accepted

Solution code:
inf=10**10
n,m=map(int,input().split())
x=[inf]*n
con=[[] for _ in range(n)]
for i in range(m):
	l,r,d=map(int,input().split())
	con[l-1].append((r-1,d))
	con[r-1].append((l-1,-d))
from collections import deque
for i in range(n):
	if x[i]==inf:
		x[i]=0
		q=deque([i])
		while q:
			e=q.pop()
			for j,k in con[e]:
				if x[j]==inf:
					q.append(j)
					x[j]=x[e]+k
				elif x[j]!=x[e]+k:
					print("No")
					exit()
print("Yes")

Submission status: Accepted

Solution code:
inf=10**10
n,m=map(int,input().split())
x=[inf]*n
con=[[] for _ in range(n)]
for i in range(m):
	l,r,d=map(int,input().split())
	con[l-1].append((r-1,d))
	con[r-1].append((l-1,-d))
from collections import deque
for i in range(n):
	if x[i]==inf:
		x[i]=0
		q=deque([i])
		while q:
			e=q.pop()
			for j,k in con[e]:
				if x[j]==inf:
					q.append(j)
					x[j]=x[e]+k
for i in range(n):
	for j,k in con[i]:
		if x[i]+k!=x[j]:
			print("No")
			exit()
print("Yes")

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Fri Mar 20 18:02:18 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

class WUnionFind:
    def __init__(self, n, sum_unity=0):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.diff_weight = [sum_unity for _ in range(n)]
        self._size = [1 for _ in range(n)]
        self._edges = 0

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            r = self.find(self.par[x])
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = r
            return r
        
    def unite(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.diff_weight[x] = -w
            self._size[y] += self._size[x]
            self._edges += 1
        else:
            self.par[y] = x
            self.diff_weight[y] = w
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self._size[x] += self._size[y]
            self._edges += 1

    def weight(self, x):
        self.find(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        return self.weight(y) - self.weight(x)
    
    def size(self, x):
        x = self.find(x)
        return self._size[x]
    
    def trees(self):
        return self.n - self._edges

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

n, m = na()
lrd = nan(m)
wuf = WUnionFind(n)
flag = True
for i in range(m):
    l, r, d = lrd[i]
    l -= 1
    r -= 1
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            flag = False
    else:
        wuf.unite(l, r, d)

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

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

graph = [[] for i in range(N)]

for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    graph[L].append([R,D])
    graph[R].append([L,-D])
    
data = [None]*N

for i in range(N):
    if data[i] != None:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y[0]] == None:
                data[y[0]] = data[x] + y[1]
                stack.append(y[0])
            else:
                if data[y[0]] - data[x] != y[1]:
                    print("No")
                    sys.exit()
    
print("Yes")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

def main(): 
    n,m = map(int,input().split())
    L = [[] for _ in range(n)]
    R = [[] for _ in range(n)]
    for _ in range(m):
        l,r,d = map(int,input().split())
        l -= 1
        r -= 1
        L[l].append((r,d))
        R[r].append((l,d))
    
    visited = [True] * n
    X = [0] * n

    def dfs(i):
        ans = True
        for r in L[i]:
            j, d = r
            if visited[j]:
                X[j] = X[i] + d
                visited[j] = False
                ans = (ans&dfs(j)) 
            else:
                if X[j] - X[i] != d:
                    ans = False
                    break
        for l in R[i]:
            j,d = l
            if visited[j]:
                X[j] = X[i] - d
                visited[j] = False
                ans = (ans&dfs(j))
            else:
                if X[i] - X[j] != d:
                    ans = False
                    break
        return ans
    
    ans = True
    for i in range(n):
        if visited[i]:
            visited[i] = False
            ans = (ans&dfs(i))
    
    if ans:
        print('Yes')
    else:
        print('No')        
  
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
pos = [-10**10 for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,-d))
stack = []
flg = 1
for i in range(1,n+1):
  if graph[i] and pos[i] == -10**10:
    stack.append(i)
    pos[i] = 0
    while stack:
      x = stack.pop()
      for y,d in graph[x]:
        if pos[y] == -10**10:
          pos[y] = pos[x]+d
          stack.append(y)
        else:
          if pos[y] != pos[x]+d:
            flg = 0
if flg:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""

N,M=map(int,input().split())
LRD=[list(map(int,input().split())) for i in range(M)]

data=[[] for i in range(N+1)]
for m,(l,r,d) in enumerate(LRD):
    data[l].append([r,d,m])
    data[r].append([l,-d,m])
data2=[set([m[1] for m in data[i]]) for i in range(N+1)]
Nlst=set([i for i in range(1,N)])
Mlst=set([i for i in range(M)])
visited=set()
X=[0 for i in range(N+1)]
while Mlst:
    stack=[Nlst.pop()]
    while stack:
        l=stack.pop()
        visited.add(l)
        for r,d,m in data[l]:
            if m in Mlst:
                Mlst.remove(m)
                if not r in visited:
                    visited.add(r)
                    X[r]=X[l]+d
                    stack.append(r)

                else:
                    if X[r]!=X[l]+d:
                        print("No")
                        exit()

print("Yes")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def dfs(v, d):
    if visited[v] and X[v] != d:
        return False
    if visited[v] and X[v] == d:
        return True
    visited[v] = True
    X[v] = d
    for u, c in E[v]:
        if not dfs(u, d + c):
            return False
    return True

N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    E[l].append((r, d))
    E[r].append((l, -d))
X = [None] * N
visited = [False] * N
for v in range(N):
    if not visited[v]:
        if not dfs(v, 0):
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
import queue
N,M=map(int,input().split())
s=[[]for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))

q=queue.Queue()
dist=[None]*N

for i in range(N):
    if dist[i]==None:
        dist[i]=0
        q.put(i)
    while not q.empty():
        From=q.get()
        for l in s[From]:
            To,w=l
            if dist[To]==None:
                dist[To]=dist[From]+w
                q.put(To)
            else:
                if dist[To]!=dist[From]+w:
                    print("No")
                    exit()
print("Yes")

Submission status: Accepted

Solution code:
INF = 10**20
N,M = map(int,input().split())
node = [[] for _ in range(N)]
for _ in range(M):
  l,r,d = map(int,input().split())
  node[l-1].append([r-1,d])
  node[r-1].append([l-1,-1*d])
 
ans = "Yes"
pos = [INF]*N
for i in range(N):
  if pos[i]==INF:
    que = [[i,0]]
    while(que):
      c,cp = que.pop()
      if pos[c]==INF:
        pos[c] = cp
        for n,d in node[c]:
          if pos[n]==INF:
            que.append([n,cp+d])
          elif pos[n] != cp+d:
            ans="No"
            break
        else:
          continue
        break
      elif pos[c] != cp:
        ans="No"
        break
    else:
      continue
    break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M, *L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
llog = set()
rlog = set()
for l,r,d in zip(*[iter(L)]*3):
  dic[l].append((r,d))
  llog.add(l)
  rlog.add(r)
log = llog.difference(rlog)
q = deque(log)
dist = [-1]*(N+1)
for c in log:
  dist[c] = 0
while q:
  v = q.popleft()
  flag = False
  for u,d in dic[v]:
    if dist[u]==-1:
      dist[u] = dist[v]+d
      q.append(u)
    elif dist[u]!=dist[v]+d:
      print('No')
      flag = True
      break
  if flag:
    break
else:
  U = llog.union(rlog)
  for c in U:
    if dist[c]==-1:
      print('No')
      break
  else:
    print('Yes')