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:
def move(related_people, fa):
  for person in related_people:
    if person not in moved:
      if fa == 1:
        locations[person] += exceeded_dist
      else:
        locations[person] -= exceeded_dist
      moved.append(person)
      move(relation[person], fa)

from collections import defaultdict

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

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

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

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

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

# 各人の関係グラフ
relation = defaultdict(lambda: [])

moved = []

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

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

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

    continue

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

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

      # 右側の人物と関連している人を全てずらす
      moved = [info["left"]]
      move(relation[info["right"]], 1)
      moved = []

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

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

    continue


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

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

      moved = [info["right"]]
      move(relation[info["left"]], 2)
      moved = []

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

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

    continue

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

      fulfill_conditions = False
      break

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

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

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
if M == 0:
    print("Yes")
    exit()

P = [list(map(int,input().split())) for _ in range(M)]
flag = True
p = P[0][0]
q = P[0][1]
r = P[0][2]
s = [-1] * 10 ** 7
t = 10**5
s[t] = P[0][0]

for i in range(M):
    if P[i][0] in s and P[i][1] in s:
        if s.index(P[i][1]) - s.index(P[i][0]) != P[i][2]:
            flag = False
        else:
            continue
    elif P[i][0] in s:
        s[s.index(P[i][0]) + P[i][2] + t] = P[i][1]
    elif P[i][1] in s:
        s[s.index(P[i][1]) - P[i][2] + t] = P[i][0]

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
N, M = map(int, raw_input().split())
l, r, d = [], [], []

for _ in range(M):
    _l, _r, _d = map(int, raw_input().split())
    l.append(_l)
    r.append(_r)
    d.append(_d)

X = np.zeros((N, ), dtype=np.int64)
is_accessed = np.zeros((N, ), dtype=np.bool)

if M > 0:
    # X[l[0]] = 0
    X[r[0] - 1] = d[0]
    is_accessed[r[0] - 1], is_accessed[l[0] - 1] = True, True
    # print X, is_accessed
    for i in range(1, M):
        if is_accessed[l[i] - 1] and is_accessed[r[i] - 1]:
            if X[r[i] - 1] != X[l[i] - 1] + d[i]:
                print 'No'
                exit()
        # elif is_accessed[r[i] - 1] and not is_accessed[l[i] - 1]:
        elif is_accessed[r[i] - 1]:
            X[l[i] - 1] = X[r[i] - 1] - d[i]
            is_accessed[l[i] - 1] = True
        # elif is_accessed[l[i] - 1] and not is_accessed[r[i] - 1]:
        elif is_accessed[l[i] - 1]:
            X[r[i] - 1] = X[l[i] - 1] + d[i]
            is_accessed[r[i] - 1] = True
        else:
            X[r[i] - 1] = d[i]
            is_accessed[r[i] - 1], is_accessed[l[i] - 1] = True, True
        # print X, is_accessed

if np.max(X) - np.min(X) > 1000000000:
    print 'No'

print 'Yes'

Submission status: Wrong Answer

Solution code:
def move(related_people, fa):
  for person in related_people:
    if person not in moved:
      if fa == 1:
        locations[person] += exceeded_dist
      else:
        locations[person] -= exceeded_dist
      moved.append(person)
      move(relation[person], fa)

from collections import defaultdict

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

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

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

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

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

# 各人の関係グラフ
relation = defaultdict(lambda: [])

moved = []

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

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

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

    continue

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

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

      # 右側の人物と関連している人を全てずらす
      move(relation[info["right"]], 1)
      moved = []

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

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

    continue


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

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

      move(relation[info["left"]], 2)
      moved = []

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

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

    continue

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

      fulfill_conditions = False
      break

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

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

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split()]
res = 'Yes'
nd = 10 ** 9
x = [nd] * (n + 1)
rd = [[] for x in range(n + 1)]
for k in range(m):
  L, r, d = [int(x) for x in input().split()]
  if L < r:
    rd[L].append([r, d])
  else:
    rd[r].append([L, -d])

first = True
fi = 0
for i in range(1, n + 1):
  if res == 'No':
    break
  for dd in rd[i]:
    r = dd[0]
    d = dd[1]
    if first:
      x[i] = 0
      x[r] = x[i] + d
      fi = i
      first = False
    else:
      v = x[i] + d
      if x[i] != nd and x[r] != nd:
        if x[i] + d != x[r]:
          res = 'No'
          break
      elif x[r] == nd:
        x[r] = x[i] + d
      else:
        x[r] = v
print(res)

Submission status: Wrong Answer

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

VAL = 100

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

dic = {}

for i in range(M):
    l = arr[i][0]
    r = arr[i][1]
    d = arr[i][2]
    isr = False
    isl = False
    if r in dic:
        key_r = dic[r]
        isr = True
    if l in dic:
        key_l = dic[l]
        isl = True

    if isr and not isl:
        dic[l] = key_r - d
    elif not isr and isl:
        dic[r] = key_l + d
    elif isr and isl:
        if key_r - key_l != d:
            print "No"
            sys.exit()
    else:
        dic[r] = r
        dic[l] = r - d


print "Yes"

Submission status: Wrong Answer

Solution code:
import sys 

temp=input().split(" ")
n=int(temp[0])
m=int(temp[1])
# p=[[-1 for i in range(n)] for j in range(n)]
p=[]
dis=[-1]*(n+5000)
for i in range(m):
    temp=input()
    temp=list(map(int,temp.split(" ")))
    p.append(temp)
p.sort()
if m!=0:
   
    for temp in p:
        x=int(temp[0])
        y=int(temp[1])    
        d=int(temp[2])
        if dis[x]==-1 and dis[y]==-1: #完全な新情報なら
            dis[x]=0
            dis[y]=d
        elif dis[x]==-1: #xだけ不明なら
            dis[x]=dis[y]-d
        elif dis[y]==-1:
            dis[y]=dis[x]+d
        if dis[y]!=dis[x]+d:
            # print (x)
            # print (y)
            # print (d)
            print("No")
            sys.exit()
print("Yes")

Submission status: Wrong Answer

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

pars = [None for _ in range(N)]
dists = [0 for _ in range(N)]


def find_root(x, d):
    if pars[x] is None:
        return None, None
    elif pars[x] == x:
        return x, dists[x] + d
    else:
        root, dist_to_root = find_root(pars[x], dists[x])
        pars[x] = root
        dists[x] = dist_to_root + d
        return pars[x], dists[x]


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

    if pars[L] is not None and pars[R] is not None:
        rootL, distL = find_root(L, 0)
        rootR, distR = find_root(R, 0)

        if rootL == rootR:
            if distL + D != distR:
                print('No')
                exit(0)
        else:
            if L < rootR:
                pars[R] = L
                dists[R] = D
            else:
                pars[L] = rootR
                dists[L] = distR - D

    elif pars[L] is not None:
        pars[R] = pars[L]
        dists[R] = D + dists[L]

    elif pars[R] is not None:
        rootR, distR = find_root(R, 0)
        if L < rootR:
            pars[R] = L
            dists[R] = D
            pars[L] = L
            dists[L] = 0
        else:
            pars[L] = rootR
            dists[L] = distR - D

    else:
        pars[R] = L
        dists[R] = D

        pars[L] = L
        dists[L] = 0

    # print(pars)
    # print(dists)
    # print()

print('Yes')

Submission status: Wrong Answer

Solution code:
def move(related_people, fa):
  for person in related_people:
    if person not in moved:
      if fa == 1:
        locations[person] += exceeded_dist
      else:
        locations[person] -= exceeded_dist
      moved.append(person)
      move(relation[person], fa)

from collections import defaultdict

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

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

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

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

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

# 各人の関係グラフ
relation = defaultdict(lambda: [])

moved = []

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

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

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

    continue

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

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

      # 右側の人物と関連している人を全てずらす
      move(relation[info["right"]], 1)
      moved = []

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

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

    continue


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

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

      move([], relation[info["left"]], 2)
      moved = []

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

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

    continue

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

      fulfill_conditions = False
      break

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

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,raw_input().split(" "))

data = []
if m == 0:
  print "Yes"
  exit(0)

for a in range(m):
  l,r,d = map(int,raw_input().split(" "))
  if l > r:
    data.append([r,l,-d])
  else:
    data.append([l,r,d])
data.sort()

p = {}

for q in range(len(data)):
  if data[q][0] not in p:
    p[data[q][0]] = -1
    r = q
    while r != len(data) and data[r][0] == data[q][0]:
      if data[r][1] in p:
        p[ data[q][0] ] = data[r][1] - data[r][2]
        break
      r += 1
    if p[data[q][0]] == -1:
      p[data[q][0]] = 0
    
  if data[q][1] in p:
    if p[ data[q][1] ] != p[ data[q][0] ] + data[q][2]:
      print "No"
      exit(0)
  p[ data[q][1] ] = p[ data[q][0] ] + data[q][2]

print "Yes"

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
N, M = map(int, raw_input().split())
l, r, d = [], [], []

for _ in range(M):
    _l, _r, _d = map(int, raw_input().split())
    l.append(_l)
    r.append(_r)
    d.append(_d)

X = np.zeros((N, ), dtype=np.int64)
is_accessed = np.zeros((N, ), dtype=np.bool)

if M > 0:
    # X[l[0]] = 0
    X[r[0] - 1] = d[0]
    is_accessed[r[0] - 1], is_accessed[l[0] - 1] = True, True
    print X, is_accessed
    for i in range(1, M):
        if is_accessed[l[i] - 1] and is_accessed[r[i] - 1]:
            if X[r[i] - 1] != X[l[i] - 1] + d[i]:
                print 'No'
                exit()
        # elif is_accessed[r[i] - 1] and not is_accessed[l[i] - 1]:
        elif is_accessed[r[i] - 1]:
            X[l[i] - 1] = X[r[i] - 1] - d[i]
            is_accessed[l[i] - 1] = True
        # elif is_accessed[l[i] - 1] and not is_accessed[r[i] - 1]:
        elif is_accessed[l[i] - 1]:
            X[r[i] - 1] = X[l[i] - 1] + d[i]
            is_accessed[r[i] - 1] = True
        else:
            X[r[i] - 1] = d[i]
            is_accessed[r[i] - 1], is_accessed[l[i] - 1] = True, True
        print X, is_accessed

if np.max(X) - np.min(X) > 1000000000:
    print 'No'

print 'Yes'

Submission status: Wrong Answer

Solution code:
import sys 

temp=input().split(" ")
n=int(temp[0])
m=int(temp[1])
# p=[[-1 for i in range(n)] for j in range(n)]
p=[]
dis=[-1]*(n+5000)
for i in range(m):
    temp=input()
    temp=list(map(int,temp.split(" ")))
    p.append(temp)
p.sort()
if m!=0:
    temp=p[0]
    x=int(temp[0])
    y=int(temp[1])
    d=int(temp[2])
    dis[x]=0
    dis[y]=d

    p.pop(0)

    for temp in p:
        x=int(temp[0])
        y=int(temp[1])    
        d=int(temp[2])
        if dis[x]==-1 and dis[y]==-1: #完全な新情報なら
            dis[x]=0
            dis[y]=d
        elif dis[x]==-1: #xだけ不明なら
            dis[x]=dis[y]-d
        elif dis[y]==-1:
            dis[y]=dis[x]+d
        if dis[y]!=dis[x]+d:
            # print (x)
            # print (y)
            # print (d)
            print("No")
            sys.exit()
print("Yes")

Submission status: Wrong Answer

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

VAL = 100

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

dic = {}

for i in range(M):
    l = arr[i][0]
    r = arr[i][1]
    d = arr[i][2]
    isr = False
    isl = False
    if r in dic:
        key_r = dic[r]
        isr = True
    if l in dic:
        key_l = dic[l]
        isl = True

    if isr and not isl:
        dic[l] = key_r - d
    elif not isr and isl:
        dic[r] = key_l + d
    else:
        dic[r] = r
        dic[l] = r - d

    if isr and isl:
        if key_r - key_l != d:
            print "No"
            sys.exit()
    #print dic

print "Yes"

Submission status: Wrong Answer

Solution code:
import numpy as np

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

if M == 0:
    print("Yes")
else:
    C = np.array([list(map(int, input().split())) for _ in range(M)])

    # for m in range(M):
    #     if C[m][1] < C[m][0]:
    #         C[m][0], C[m][1] = C[m][1], C[m][0]
    #         C[m][2] = -C[m][2]
    # C = C[C[:, 0].argsort(), :]

    checked = {m: False for m in range(1, M + 1)}
    pos = {n: False for n in range(1, N + 1)}
    flag = True
    flagContinue = True
    while flagContinue:
        for m in range(M):
            if not checked[m + 1]:
                if pos[C[m][0]] is False and pos[C[m][1]] is False:
                    pos[C[m][0]] = 0
                    pos[C[m][1]] = C[m][2]
                elif pos[C[m][0]] is not False and pos[C[m][1]] is not False:
                    if pos[C[m][1]] - pos[C[m][0]] != C[m][2]:
                        flag = False
                        checked = {m: True for m in range(1, M + 1)}
                        break
                elif pos[C[m][0]] is False:
                    pos[C[m][0]] = pos[C[m][1]] - C[m][2]
                else:
                    pos[C[m][1]] = pos[C[m][0]] + C[m][2]
                checked[m + 1] = True
        flagContinue = False
        for m in range(1, M + 1):
            if not checked[m]:
                flagContinue = True
                break

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

Submission status: Wrong Answer

Solution code:
def move(moved, related_people, type):
  for person in related_people:
    if person not in moved:
      if type == 1:
        locations[person] += exceeded_dist
      else:
        locations[person] -= exceeded_dist
      moved.append(person)
      move(moved, relation[person], type)

from collections import defaultdict

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

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

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

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

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

# 各人の関係グラフ
relation = defaultdict(lambda: [])

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

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

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

    continue

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

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

      # 右側の人物と関連している人を全てずらす
      move([], relation[info["right"]], 1)

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

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

    continue


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

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

      move([], relation[info["left"]], 2)

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

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

    continue

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

      fulfill_conditions = False
      break

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

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

Submission status: Wrong Answer

Solution code:
N,M=input().split()
N,M=int(N),int(M)
info=[[int(i)-1 for i in input().split()] for i in range(M)]
X=['null']*N
detalist=[]
judge=0
for i in range(M):
    if info[i][0] not in detalist:
        X[info[i][0]]=0
        detalist.append(info[i][0])
    if info[i][1] not in detalist:
        X[info[i][1]]=X[info[i][0]]+info[i][2]
        detalist.append(info[i][1])
    if info[i][0] and info[i][1] in detalist:
        if X[info[i][1]]!=X[info[i][0]]+info[i][2]:
            judge=1
    if judge==1:
        print("No")
        break
if judge==0:print("Yes")

Submission status: Wrong Answer

Solution code:
import numpy as np

n, m = map(int, input().split(" "))
l = np.zeros(m, dtype=np.int)
r = np.zeros(m, dtype=np.int)
d = np.zeros(m, dtype=np.int)
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split(" "))

pos = np.zeros(n, dtype=np.int)

for i in range(m):
    if(pos[l[i]-1] == 0 and pos[r[i]-1] == 0):
        pos[l[i]-1] = 1
        pos[r[i]-1] = pos[l[i]-1] + d[i]
    elif(pos[l[i]-1] != 0 and pos[r[i]-1] == 0):
        pos[r[i]-1] = pos[l[i]-1] + d[i]
    elif(pos[l[i]-1] == 0 and pos[r[i]-1] != 0):
        pos[l[i]-1] = pos[r[i]-1] - d[i]
    else:
        if(abs(pos[r[i]-1] - pos[l[i]-1]) != d[i]):
            print("No")
            exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
def move(moved, related_people):

  for person in related_people:
    if person not in moved:
      locations[person] += exceeded_dist
      moved.append(person)
      move(moved, relation[person])



from collections import defaultdict

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

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

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

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

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

# 各人の関係グラフ
relation = defaultdict(lambda: [])

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

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

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

    continue

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

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

      # 右側の人物と関連している人を全てずらす
      move([], relation[info["right"]])

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

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

    continue


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

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

      move([], relation[info["left"]])

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

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

    continue

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

      fulfill_conditions = False
      break

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

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

Submission status: Wrong Answer

Solution code:
# coding=utf-8

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

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

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

def check(l):
    nl = [None for x in range(N)]
    nl[0] = 0

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

while len(l)>0:
    l = check(l)
    if len(l)==0:
        break
    l.sort()
    o = l[0][0]
    for i in range(len(l)):
        l[i] = (
            l[i][0]-o
            ,l[i][1]-o
            ,l[i][2]
        )


print("Yes")

Submission status: Wrong Answer

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

VAL = 100

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

dic = {}

for i in range(M):
    l = arr[i][0]
    r = arr[i][1]
    d = arr[i][2]
    isr = False
    isl = False
    if r in dic:
        key_r = dic[r]
        isr = True
    if l in dic:
        key_l = dic[l]
        isl = True

    if isr and not isl:
        dic[l] = isr - d
    elif not isr and isl:
        dic[r] = isl + d
    else:
        dic[r] = r
        dic[l] = r - d

    if isr and isl:
        if key_r - key_l != d:
            print "No"
            sys.exit()

print "Yes"

Submission status: Wrong Answer

Solution code:
N,M=input().split()
N,M=int(N),int(M)
info=[[int(i)-1 for i in input().split()] for i in range(M)]
X=['null']*N
judge=1
detalist=[]
for i in range(M):
    if info[i][0] not in detalist:
        X[info[i][0]]=0
        detalist.append(info[i][0])
    if info[i][1] not in detalist:
        X[info[i][1]]=X[info[i][0]]+info[i][2]
        detalist.append(info[i][1])
    if info[i][0] and info[i][1] in detalist:
        if X[info[i][1]]!=X[info[i][0]]+info[i][2]:
            judge=0
if judge==1:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
x = {}
n, m = map(int, raw_input().split())
flag = True
dat = sorted([map(int, raw_input().split()) for _ in xrange(m)], key = lambda x: x[0])
for l, r, d in dat:
    if l not in x and r not in x:
        x[l], x[r] = (l, 0), (l, d)
    elif r in x and l not in x:
        x[l] = (x[r][0], x[r][1] - d)
    elif l in x and r not in x:
        x[r] = (x[l][0], x[l][1] + d)
    else:
        if x[r][1] - x[l][1] != d:
            flag = False
            break
print 'Yes' if flag else 'No'