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:
# D - People on a Line
from heapq import heappush,heappop

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
# https://at274.hatenablog.com/entry/2018/02/03/140504
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

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

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

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

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

N,M=map(int,input().split())
uf = WeightedUnionFind(N+1)
for i in range(M):
  l,r,d=map(int,input().split())
  if l>r:
    l,r=r,l
    d=-d
  uf.union(l,r,d)
  if d != uf.diff(l,r):
    print('No')
    exit()
print('Yes')

Submission status: Wrong Answer

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


class UnionFindWeighted:
    # Reference: https://note.nkmk.me/python-union-find/
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.weight = [0] * n

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

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

        if self.parents[rx] > self.parents[ry]:
            rx, ry, w = ry, rx, -w

        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        self.weight[ry] = self.weight[x] - self.weight[y] - w

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

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


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

    uf = UnionFindWeighted(N)
    for l, r, d in zip(*[iter(LRD)] * 3):
        l -= 1
        r -= 1
        if uf.same(l, r) and uf.diff(l, r) != d:
            print('No')
            return
        else:
            uf.union(l, r, d)

    print('Yes')
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


class UnionFindWeighted:
    # Reference: https://note.nkmk.me/python-union-find/
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.weight = [0] * n

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

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

        if rx == ry:
            d = self.diff(x, y)
            if d == w:
                return
            else:
                raise ValueError(
                    f"The given weight {w} from {x} to {y} is not consistent with the current weight {d}"
                )

        if self.parents[rx] > self.parents[ry]:
            rx, ry, w = ry, rx, -w

        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        self.weight[ry] = self.weight[x] - self.weight[y] - w

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

    def diff(self, x, y):
        if self.find(x) == self.find(y):
            return self.weight[x] - self.weight[y]
        else:
            raise ValueError(f"{x} and {y} do not belong to the same root")


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

    uf = UnionFindWeighted(N)
    for l, r, d in zip(*[iter(LRD)] * 3):
        l -= 1
        r -= 1
        if uf.same(l, r) and uf.diff(l, r) != d:
            print('No')
            return
        else:
            uf.union(l, r, d)

    print('Yes')
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import queue
n,m=map(int,input().split())
a=[[]for _ in range(n+1)]
for _ in range(m):
  l,r,d=map(int,input().split())
  a[l]+=[(r,d)]
d=[-1]*(n+1)
for i in range(n+1):
  if a[i]:
    if d[i]==-1:d[i]=0
    for to,dis in a[i]:
      if d[to]==-1:d[to]=d[i]+dis
      else:
        if d[to]!=d[i]+dis:
          print('No')
          exit()
print('Yes')

Submission status: Wrong Answer

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

for i in range(N):
  if root[i] < -10 ** 9 - 1:
    root[i] = 0
      
x = min(root)
y = max(root)
if y - x > 10 **9:
  print("No")
  quit()
  
  
      
print("Yes")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#組を一つつくればいいよ
INF = -10**15

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

LRD = []
for i in range(M):
    L,R,D = map(int,input().split())
    L,R = min(L,R),max(L,R)
    LRD.append([L,R,D])
LRD.sort()

ans=True
position = [INF]*(N+1)
for i in range(M):
    L,R,D = LRD[i]
    if position[L]==INF and position[R]==INF:
        position[L]=0
        position[R]=position[L]+D
    else:
        if position[L]==INF:
            position[L]=position[R]-D
        elif position[R]==INF:
            position[R]=position[L]+D
        else:
            if position[R]-position[L]!=D:
                ans=False
                break

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

Submission status: Wrong Answer

Solution code:
#組を一つつくればいいよ
INF = -10**15

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

LRD = []
for i in range(M):
    L,R,D = map(int,input().split())
    L,R = min(L,R),max(L,R)
    LRD.append([L,R,D])
LRD.sort()

ans=True
position = [INF]*(N+1)
for i in range(M):
    L,R,D = LRD[i]
    if position[L]==INF:
        position[L]=0
    if position[R]==INF:
        position[R]=position[L]+D
    else:
        if position[R]!=position[L]+D:
            ans=False
            break
print("Yes" if ans else "No")

Submission status: Wrong Answer

Solution code:
#組を一つつくればいいよ
INF = -10**15

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

LRD = []
for i in range(M):
    L,R,D = map(int,input().split())
    L,R = min(L,R),max(L,R)
    LRD.append([L,R,D])
LRD.sort()

ans=True
position = [INF]*(N+1)
for i in range(M):
    L,R,D = LRD[i]
    print(L,R,D)
    if position[L]==INF:
        position[L]=0
    if position[R]==INF:
        position[R]=position[L]+D
    else:
        if position[R]!=position[L]+D:
            ans=False
            break
print("Yes" if ans else "No")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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


n, m = inm()
INF = 10 ** 12


def solve():
    pos = [None] * n
    uf = UnionFind(n)
    for i in range(m):
        l, r, d = inm()
        l -= 1
        r -= 1
        uf.union(l, r)
        if pos[l] is None and pos[r] is None:
            pos[l] = 0
            pos[r] = d
        elif pos[r] is None:
            pos[r] = pos[l] + d
        elif pos[l] is None:
            pos[l] = pos[r] - d
        elif pos[r] - pos[l] != d:
            return False
    mins = defaultdict(lambda: INF)
    maxs = defaultdict(lambda: -INF)

    for i in range(n):
        r = uf.find(i)
        if r != i:
            mins[r] = min(mins[r], pos[i])
            maxs[r] = max(maxs[r], pos[i])

    for r in mins.keys():
        if maxs[r] - mins[r] > 10 ** 9:
            return False
    return True


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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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


n, m = inm()


def solve():
    pos = [None] * n
    for i in range(m):
        l, r, d = inm()
        l -= 1
        r -= 1
        if pos[l] is None and pos[r] is None:
            pos[l] = 0
            pos[r] = d
        elif pos[r] is None:
            pos[r] = pos[l] + d
        elif pos[l] is None:
            pos[l] = pos[r] - d
        elif pos[r] - pos[l] != d:
            return False
    return True


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    uf = UnionFind(N+1)
    try:
        for l, r, d in zip(L, R, D):
            uf.merge(l, r, d)
        return YES
    except MergeError:
        return NO

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    D = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    print(solve(N, M, L, R, D))
    
class MergeError(Exception):
    pass

# 参考: https://qiita.com/drken/items/cce6fc5c579051e64fab
class UnionFind:
    def __init__(self, size: int):
        self.par = list(range(size))
        self.rank = [0] * size
        self.diff_weight = [0] * size

    def root(self, x: int):
        if self.par[x] == x:
            return x
        r = self.root(self.par[x])
        self.diff_weight[x] += self.diff_weight[self.par[x]] # 累積和をとる        
        #return par[x] := r
        self.par[x] = r
        return r

    def weight(self, x: int):
        self.root(x) # 経路圧縮
        return self.diff_weight[x]

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

    # weight(y) - weight(x) = w となるように merge する
    def merge(self, x: int, y: int, w: int):
        # x と y それぞれについて、 root との重み差分を補正
        adjusted_w = w + self.weight(x) - self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y:
            if adjusted_w != 0:
                raise MergeError
            return
        if self.rank[x] < self.rank[y]:
            x, y, w = y, x, -adjusted_w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        self.diff_weight[y] = adjusted_w

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
dist = [[] for i in range(N)]
for i in range(M):
    l, r, d = getNM()
    dist[l - 1].append([r - 1, d])
    dist[r - 1].append([l - 1, -d])

dis = [float('inf')] * N

pos = deque([i for i in range(N) if len(dist[i]) > 0])
while len(pos) > 0:
    u = pos.popleft()
    # 始めの第一歩
    if dis[u] == float('inf'):
        dis[u] = 0
    # 行き先の位置が未確定なら確定させる
    # 既に確定しているなら判定
    for to, d in dist[u]:
        if dis[to] == float('inf'):
            dis[to] = dis[u] + d
            pos.append(to)
        else:
            if dis[u] + d != dis[to]:
                print('No')
                exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
dist = [[] for i in range(N)]
for i in range(M):
    l, r, d = getNM()
    dist[l - 1].append([r - 1, d])
    dist[r - 1].append([l - 1, -d])

dis = [float('inf')] * N

pos = deque([i for i in range(N)])
while len(pos) > 0:
    u = pos.popleft()
    # 始めの第一歩
    if dis[u] == float('inf'):
        dis[u] = 0
    # 行き先の位置が未確定なら確定させる
    # 既に確定しているなら判定
    for to, d in dist[u]:
        if dis[to] == float('inf'):
            dis[to] = dis[u] + d
            pos.append(to)
        else:
            if dis[u] + d != dis[to]:
                print('No')
                exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    uf = UnionFind(N+1)
    try:
        for l, r, d in zip(L, R, D):
            uf.merge(l, r, d)
        return YES
    except MergeError:
        return NO

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    D = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    print(solve(N, M, L, R, D))
    
class MergeError(Exception):
    pass

# 参考: https://qiita.com/drken/items/cce6fc5c579051e64fab
class UnionFind:
    def __init__(self, size: int):
        self.par = list(range(size))
        self.rank = [0] * size
        self.diff_weight = [0] * size

    def root(self, x: int):
        if self.par[x] == x:
            return x
        r = self.root(self.par[x])
        self.diff_weight[x] += self.diff_weight[self.par[x]] # 累積和をとる        
        #return par[x] := r
        self.par[x] = r
        return r

    def weight(self, x: int):
        self.root(x) # 経路圧縮
        return self.diff_weight[x]

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

    # weight(y) - weight(x) = w となるように merge する
    def merge(self, x: int, y: int, w: int):
        # x と y それぞれについて、 root との重み差分を補正
        adjusted_w = w + self.weight(x) - self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y:
            if adjusted_w != 0:
                raise MergeError
            return
        if self.rank[x] < self.rank[y]:
            x, y, w = y, x, -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        self.diff_weight[y] = adjusted_w

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))
g=[[] for _ in range(n+1)]
visited=[0]*(n+1)
x=[0]*(n+1)

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

    g[r].append((l,d))
    g[l].append((r,-d))

stack=[1]

while len(stack)>0:
    u=stack.pop()

    visited[u]=1

    for v,d in g[u]:
        if visited[v]==1:
            continue

        x[v]=x[u]-d

        stack.append(v)

flag=True

for i in range(1,n+1):
    for j,d in g[i]:
        if x[i]-x[j]!=d:
            flag=False

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

Submission status: Wrong Answer

Solution code:
n,m= map(int,input().split())
groups=[]
wgroup=[-1]*(n+1)
dist = [-1]*(n+1)
newgroupid=0
er=False
for i in range(m):
    l,r,d= map(int,input().split())
    if er:pass 
    else:
        if wgroup[l]==-1 and wgroup[r]==-1: #l and r no group
            agroup = set()
            agroup.add(l)
            agroup.add(r)
            dist[l]=0
            dist[r]=d
            groups.append(agroup)
            wgroup[l]=newgroupid
            wgroup[r]=newgroupid
            newgroupid+=1
        elif wgroup[l]!=-1 and wgroup[r]==-1: #r to l-group
            groups[wgroup[l]].add(r)
            dist[r]=dist[l]+d
            wgroup[r]=wgroup[l]
        elif wgroup[l]==-1 and wgroup[r]!=-1: #l to r-group
            groups[wgroup[r]].add(l)
            dist[l]=dist[r]-d
            wgroup[l]=wgroup[r]
        else:
            if wgroup[l]==wgroup[r]:#同じグループである。
                if d!=dist[r]-dist[l]:er=True
            else:
                if len(groups[wgroup[l]]) >= len(groups[wgroup[r]]):
                    diff = (dist[l] + d) - dist[r]
                    for c in groups[wgroup[r]]:
                        dist[c] += diff
                        wgroup[c]=wgroup[r]
                    newset = groups[wgroup[l]] | groups[wgroup[r]]
                    groups[wgroup[l]] = newset
                else:
                    diff = (dist[r] - d) - dist[l]
                    for c in groups[wgroup[l]]:
                        dist[c] += diff
                        wgroup[c]=wgroup[l]
                    newset = groups[wgroup[l]] | groups[wgroup[r]]
                    groups[wgroup[r]] = newset
for gr in groups:#各グループの位置最小、最大の差が10**9以内か?
    if er:pass
    else:
        tmin=9999999999
        tmax =0
        for c in gr:
            tmin = min(tmin,dist[c])
            tmax = max(tmax,dist[c])
        if tmax-tmin>10**9:
            er=True
        #else:print('dist ok')    
print('No' if er else 'Yes')

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))
inf=10**10
x=[0]*(n+1)
fixed=[0]*(n+1)
for _ in range(m):
    l,r,d=list(map(int,input().split()))

    if fixed[l]==0 and fixed[r]==0:
        x[r]=x[l]+d
        fixed[l]=1
        fixed[r]=1
    elif fixed[l] and fixed[r]:
        if x[r]-x[l]!=d:
            print('No')
            exit(0)
    elif fixed[l]==1:
        x[r]=x[l]+d
        fixed[r]=1
    else:
        x[l]=x[r]-d
        fixed[l]=1

print('Yes')