Problem:


Score : 800 points

Problem Statement

There is a grid with R rows and C columns.
We call the cell in the r-th row and c-th column (r，c).

Mr. Takahashi wrote non-negative integers into N of the cells, that is, he wrote a non-negative integer a_i into (r_i，c_i) for each i (1≤i≤N).
After that he fell asleep.

Mr. Aoki found the grid and tries to surprise Mr. Takahashi by writing integers into all remaining cells.
The grid must meet the following conditions to really surprise Mr. Takahashi.

Condition 1: Each cell contains a non-negative integer.

Condition 2: For any 2×2 square formed by cells on the grid, the sum of the top left and bottom right integers must always equal to the sum of the top right and bottom left integers.

Determine whether it is possible to meet those conditions by properly writing integers into all remaining cells.

Constraints

2≤R，C≤10^5

1≤N≤10^5

1≤r_i≤R

1≤c_i≤C

(r_i，c_i) ≠ (r_j，c_j) (i≠j)

a_i is an integer.

0≤a_i≤10^9

Input

The input is given from Standard Input in the following format:

R C
N
r_1 c_1 a_1
r_2 c_2 a_2
:
r_N c_N a_N

Output

Print Yes if it is possible to meet the conditions by properly writing integers into all remaining cells.
Otherwise, print No.

Sample Input 1

2 2
3
1 1 0
1 2 10
2 1 20

Sample Output 1

Yes

You can write integers as follows.

Sample Input 2

2 3
5
1 1 0
1 2 10
1 3 20
2 1 30
2 3 40

Sample Output 2

No

There are two 2×2 squares on the grid, formed by the following cells:

Cells (1，1), (1，2), (2，1) and (2，2)

Cells (1，2), (1，3), (2，2) and (2，3)

You have to write 40 into the empty cell to meet the condition on the left square, but then it does not satisfy the condition on the right square.

Sample Input 3

2 2
3
1 1 20
1 2 10
2 1 0

Sample Output 3

No

You have to write -10 into the empty cell to meet condition 2, but then it does not satisfy condition 1.

Sample Input 4

3 3
4
1 1 0
1 3 10
3 1 10
3 3 20

Sample Output 4

Yes

You can write integers as follows.

Sample Input 5

2 2
4
1 1 0
1 2 10
2 1 30
2 2 20

Sample Output 5

No

All cells already contain a integer and condition 2 is not satisfied.



Sample input:
2 2
3
1 1 0
1 2 10
2 1 20


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
n = int(input())
from collections import defaultdict
mind = [10**15] * h
dw = defaultdict(list)
for i in range(n):
    r,c,a = map(int, input().split())
    r -= 1
    c -= 1
    mind[r] = min(mind[r], a)
    dw[c].append((a,r))
# 0未満になる要素があるか判定
es = [[] for _ in range(h)]
def main():
    ans = True
    for c in range(w):
        if len(dw[c])<=1:
            continue
        dw[c].sort()
        tmp = 0
        for i in range(len(dw[c])-1):
            u = dw[c][i][1]
            v = dw[c][i+1][1]
            val = dw[c][i+1][0] - dw[c][i][0]
            es[u].append((val, v))
            es[v].append((-val, u))
            tmp += val
            if mind[v]<tmp:
                return False
#     print(es)
#     print(dw)
    vals = [None]*h
    for start in range(h):
        if vals[start] is not None:
            continue
        q = [start]
        vals[start] = 0
        while q:
            u = q.pop()
            for d,v in es[u]:
                if vals[v] is None:
                    vals[v] = vals[u] + d
                    q.append(v)
                elif vals[v]!=vals[u]+d:
                    return False
    for u in range(h):
        for d,v in es[u]:
            if vals[u]+d!=vals[v]:
                return False
    return True
ans = main()
if ans:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
n = int(input())
from collections import defaultdict
mind = [10**15] * h
dw = defaultdict(list)
for i in range(n):
    r,c,a = map(int, input().split())
    r -= 1
    c -= 1
    mind[r] = min(mind[r], a)
    dw[c].append((a,r))
# 0未満になる要素があるか判定
es = [[] for _ in range(h)]
def main():
    ans = True
    for c in range(w):
        if len(dw[c])<=1:
            continue
        dw[c].sort()
        tmp = 0
        for i in range(len(dw[c])-1):
            u = dw[c][i][1]
            v = dw[c][i+1][1]
            val = dw[c][i+1][0] - dw[c][i][0]
            es[u].append((val, v))
            es[v].append((-val, u))
            tmp += val
            if mind[v]<tmp:
                return False
#     print(es)
#     print(dw)
    vals = [None]*h
    for start in range(h):
        if vals[start] is not None:
            continue
        q = [start]
        vals[start] = 0
        while q:
            u = q.pop()
            for d,v in es[u]:
                if vals[v] is None:
                    vals[v] = vals[u] + d
                    q.append(v)
                elif vals[v]!=vals[u]+d:
                    return False
    return True
ans = main()
if ans:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



h,w = list(map(int, input().split()))
n = int(input())
from collections import defaultdict
mind = [10**18] * h
dw = defaultdict(list)
for i in range(n):
    r,c,a = map(int, input().split())
    r -= 1
    c -= 1
    mind[r] = min(mind[r], a)
    dw[c].append((a,r))
# 0未満になる要素があるか判定
es = [[] for _ in range(h)]
def main():
    ans = True
    for c in range(w):
        if len(dw[c])<=1:
            continue
        dw[c].sort()
        tmp = 0
        for i in range(len(dw[c])-1):
            u = dw[c][i][1]
            v = dw[c][i+1][1]
            val = dw[c][i+1][0] - dw[c][i][0]
            es[u].append((val, v))
            es[v].append((-val, u))
            tmp += val
            if mind[v]<tmp:
                return False
#     print(es)
#     print(dw)
    vals = [None]*h
    for start in range(h):
        if vals[start] is not None:
            continue
        q = [start]
        vals[start] = 0
        while q:
            u = q.pop()
            for d,v in es[u]:
                if vals[v] is None:
                    vals[v] = vals[u] + d
                elif vals[v]!=vals[u]+d:
                    return False
    return True
ans = main()
if ans:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
n = int(input())
from collections import defaultdict
mind = [10**15] * h
dw = defaultdict(list)
for i in range(n):
    r,c,a = map(int, input().split())
    r -= 1
    c -= 1
    mind[r] = min(mind[r], a)
    dw[c].append((a,r))
# 0未満になる要素があるか判定
es = [[] for _ in range(h)]
def main():
    ans = True
    for c in range(w):
        if len(dw[c])<=1:
            continue
        dw[c].sort()
        tmp = 0
        for i in range(len(dw[c])-1):
            u = dw[c][i][1]
            v = dw[c][i+1][1]
            val = dw[c][i+1][0] - dw[c][i][0]
            es[u].append((val, v))
            es[v].append((-val, u))
            tmp += val
            if mind[v]<tmp:
                return False
    else:
        vals = [None]*h
        for start in range(h):
            if vals[start] is not None:
                continue
            q = [start]
            vals[start] = 0
            while q:
                u = q.pop()
                for d,v in es[u]:
                    if vals[v] is None:
                        vals[v] = vals[u] + d
                    elif vals[v]!=vals[u]+d:
                        return False
    return True
ans = main()
if ans:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
n = int(input())
from collections import defaultdict
mind = [10**15] * h
dw = defaultdict(list)
for i in range(n):
    r,c,a = map(int, input().split())
    r -= 1
    c -= 1
    mind[r] = min(mind[r], a)
    dw[c].append((a,r))
# 0未満になる要素があるか判定
es = [[] for _ in range(h)]
def main():
    ans = True
    for c in range(w):
        if len(dw[c])<=1:
            continue
        dw[c].sort()
        tmp = 0
        for i in range(len(dw[c])-1):
            u = dw[c][i][1]
            v = dw[c][i+1][1]
            val = dw[c][i+1][0] - dw[c][i][0]
            es[u].append((val, v))
            es[v].append((-val, u))
            tmp += val
            if mind[v]<val:
                return False
    else:
        vals = [None]*h
        for start in range(h):
            if vals[start] is not None:
                continue
            q = [start]
            vals[start] = 0
            while q:
                u = q.pop()
                for d,v in es[u]:
                    if vals[v] is None:
                        vals[v] = vals[u] + d
                    elif vals[v]!=vals[u]+d:
                        return False
    return True
ans = main()
if ans:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
class UFP():
    def __init__(self, num):
        self.par = [-1]*num
        self.dist = [0]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            res = 0
            xo = x
            while self.par[x] >= 0:
                res += self.dist[x]
                x = self.par[x]
            self.dist[xo] = res
            self.par[xo] = x
            return x
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] > self.par[ry]:
                rx, ry = ry, rx
                x, y = y, x
                d = -d
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
            return True
        else:
            if d + self.dist[x] - self.dist[y]:
                return False
            return True           
    
INF = 10**9+7
def check():
    H, W = map(int, readline().split())
    N = int(readline())
    Hm = [INF]*H
    Wm = [INF]*W
    HP = [[] for _ in range(H)]
    WP = [[] for _ in range(W)]
    for _ in range(N):
        h, w, a = map(int, readline().split())
        h -= 1
        w -= 1
        Hm[h] = min(Hm[h], a)
        Wm[w] = min(Wm[w], a)
        HP[h].append((w, a))
        WP[w].append((h, a))
        
    Th = UFP(H)
    Tw = UFP(W)
    for h in range(H):
        L = len(HP[h]) 
        if L > 1:
            HP[h].sort()
            for i in range(L-1):
                wp, ap = HP[h][i]
                wn, an = HP[h][i+1]
                if not Tw.union(wp, wn, an-ap):
                    return False
    for w in range(W):
        L = len(WP[w]) 
        if L > 1:
            WP[w].sort()
            for i in range(L-1):
                hp, ap = WP[w][i]
                hn, an = WP[w][i+1]
                if not Th.union(hp, hn, an-ap):
                    return False
    for h in range(H):
        Th.find(h)
    for w in range(W):
        Tw.find(w)
    
    minh = Th.dist.index(min(Th.dist))
    for h in range(H):
        if Hm[h] == INF:
            continue
        if Hm[h] - Th.dist[h] + Th.dist[minh] < 0:
            return False
    minw = Tw.dist.index(min(Tw.dist))
    for w in range(W):
        if Wm[w] == INF:
            continue
        if Wm[w] - Tw.dist[w] + Tw.dist[minw] < 0:
            return False
    return True

print('Yes' if check() else 'No')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
R, C = map(int, input().split())
G = defaultdict(lambda:-1)
n = int(input())
RCA = [list(map(int, input().split())) for _ in range(n)]
for r, c, a in RCA:
  G[(r, c)] = a
D = [(-1, -1, -1, 0), (-1, -1, 0, -1), (-1, 0, 0, -1), (-1, 1, -1, 0), (-1, 1, 0, 1), (-1, 0, 0, 1), (1, -1, 1, 0), (1, -1, 0, -1), (1, 0, 0, -1), (1, 1, 1, 0), (1, 1, 0, 1), (1, 0, 0, 1)]
for r, c, a in RCA:
  for w, x, y, z in D:
    if G[(r+w, c+x)]!=-1 and G[(r+y, c+z)]!=-1:
      if G[(r+(w^y), c+(x^z))]==-1:
        G[(r+(w^y), c+(x^z))] = G[(r, c)]+G[(r+w, c+x)]-G[(r+y, c+z)]
        if G[(r+(w^y), c+(x^z))] < 0:
          print("No")
          exit()
      else:
        if G[(r+(w^y), c+(x^z))] != G[(r, c)]+G[(r+w, c+x)]-G[(r+y, c+z)]:
          print("No")
          exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
R, C = map(int, input().split())
G = defaultdict(lambda:-1)
n = int(input())
RCA = [list(map(int, input().split())) for _ in range(n)]
for r, c, a in RCA:
  G[(r, c)] = a
D = [(-1, -1, -1, 0), (-1, -1, 0, -1), (-1, 1, -1, 0), (-1, 1, 0, 1), (1, -1, 1, 0), (1, -1, 0, -1), (1, 1, 1, 0), (1, 1, 0, 1)]
for _ in range(2):
  for r, c, a in RCA:
    for w, x, y, z in D:
      if G[(r+w, c+x)]!=-1 and G[(r+y, c+z)]!=-1:
        if G[(r+(w^y), c+(x^z))]==-1:
          G[(r+(w^y), c+(x^z))] = G[(r, c)]+G[(r+w, c+x)]-G[(r+y, c+z)]
          if G[(r+(w^y), c+(x^z))] < 0:
            print("No")
            exit()
        else:
          if G[(r+(w^y), c+(x^z))] != G[(r, c)]+G[(r+w, c+x)]-G[(r+y, c+z)]:
            print("No")
            exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
R, C = map(int, input().split())
G = defaultdict(lambda:-1)
n = int(input())
RCA = [list(map(int, input().split())) for _ in range(n)]
for r, c, a in RCA:
  G[(r, c)] = a
D = [(-1, -1, -1, 0), (-1, -1, 0, -1), (-1, 1, -1, 0), (-1, 1, 0, 1), (1, -1, 1, 0), (1, -1, 0, -1), (1, 1, 1, 0), (1, 1, 0, 1)]
for r, c, a in RCA:
  for w, x, y, z in D:
    if G[(r+w, c+x)]!=-1 and G[(r+y, c+z)]!=-1:
      if G[(r+(w^y), c+(x^z))]==-1:
        G[(r+(w^y), c+(x^z))] = G[(r, c)]+G[(r+w, c+x)]-G[(r+y, c+z)]
        if G[(r+(w^y), c+(x^z))] < 0:
          print("No")
          exit()
      else:
        if G[(r+(w^y), c+(x^z))] != G[(r, c)]+G[(r+w, c+x)]-G[(r+y, c+z)]:
          print("No")
          exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
# 重み付き UnionFind を初めて書いた


class WeightedUnionFind:
    # https://qiita.com/drken/items/cce6fc5c579051e64fab
    def __init__(self, n, SUM_UNITY=0):
        self.par = list(range(n))
        self.rank = [0] * n
        self.diff_weight = [SUM_UNITY] * n

    def root(self, x):
        p = self.par[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.diff_weight[x] += self.diff_weight[p]
            self.par[x] = r
            return r

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

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

    def unite(self, x, y, w):
        if self.same(x, y):
            return self.diff(x, y) == w
        w += self.weight(x);  w -= self.weight(y)
        x, y = self.root(x), self.root(y)
        # if x == y:
        #     return False
        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        self.diff_weight[y] = w
        return True

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

    def get_roots_weights(self):
        roots = []
        weights = []
        for x in range(len(self.par)):
            roots.append(self.root(x))
            weights.append(self.weight(x))
        return roots, weights

import sys
from operator import itemgetter
from itertools import groupby
from collections import defaultdict

def main():
    R, C = map(int, input().split())
    N = int(input())
    RCA = list(zip(*[iter(map(int, sys.stdin.read().split()))]*3))
    uf_r = WeightedUnionFind(R+1)
    uf_c = WeightedUnionFind(C+1)

    RCA.sort(key=itemgetter(0))
    for _, g in groupby(RCA, key=itemgetter(0)):
        _, c0, a0 = next(g)
        for _, c, a in g:
            if not uf_c.unite(c0, c, a-a0):
                print("No")
                exit()

    RCA.sort(key=itemgetter(1))
    for _, g in groupby(RCA, key=itemgetter(1)):
        r0, _, a0 = next(g)
        for r, _, a in g:
            if not uf_r.unite(r0, r, a-a0):
                print("No")
                exit()

    r_roots, r_weights = uf_r.get_roots_weights()
    c_roots, c_weights = uf_c.get_roots_weights()
    r_roots_inv = defaultdict(list)
    for i, r in enumerate(r_roots):
        r_roots_inv[r].append(i)
    c_roots_inv = defaultdict(list)
    for i, r in enumerate(c_roots):
        c_roots_inv[r].append(i)
    Closed_r = set()
    Closed_c = set()
    for r, c, a in RCA:
        root_r, root_c = r_roots[r], c_roots[c]
        if root_r in Closed_r:
            assert root_c in Closed_c
            continue
        Closed_r.add(root_r)
        Closed_c.add(root_c)
        mi = float("inf")
        for v in r_roots_inv[root_r]:
            mi = min(mi, r_weights[v])
        a += mi - r_weights[root_r]
        for v in c_roots_inv[root_c]:
            a_ = a + c_weights[v] - c_weights[root_c]
            if a_ < 0:
                print("No")
                exit()
    print("Yes")

main()

Submission status: Wrong Answer

Solution code:
R,C=map(int,input().split())
N=int(input())
G=[dict() for i in range(R+C)]
for i in range(N):
    r,c,a=map(int,input().split())
    r-=1;c-=1
    G[r][R+c]=a
    G[R+c][r]=a
h=[(0,0) for i in range(R+C)]
q=[]
for i in range(R+C):
    if h[i][1]==1:
        continue
    q.append(i)
    h[i]=(0,1)
    while(len(q)>0):
        r=q.pop()
        for p in G[r]:
            tmp=(G[r][p]-h[r][0],1)
            if h[p][1]==1 and h[p]!=tmp:
                print("No")
                exit()
            else:
                if h[p][1]==0:
                    q.append(p)
            h[p]=tmp
g=[i[0] for i in h]
X=g[:R]
Y=g[R:]
if min(X)+min(Y)>=0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import queue
R,C=map(int,input().split())
N=int(input())
G=[dict() for i in range(R+C)]
for i in range(N):
    r,c,a=map(int,input().split())
    r-=1;c-=1
    G[r][R+c]=a
    G[R+c][r]=a
h=[(0,0) for i in range(R+C)]
q=queue.Queue()
for i in range(R+C):
    if h[i][1]==1:
        continue
    q.put(i)
    h[i]=(0,1)
    while(not(q.empty())):
        r=q.get()
        for p in G[r]:
            tmp=(G[r][p]-h[r][0],1)
            if h[p][1]==1 and h[p]!=tmp:
                print("No")
                exit()
            else:
                if h[p][1]==0:
                    q.put(p)
            h[p]=tmp
g=[i[0] for i in h]
X=g[:R]
Y=g[R:]
if min(X)+min(Y)>=0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

def find(x):	#xの根を返す
	global table
	global diff_weight

	if table[x] == x:
		return x
	else:
		root = find(table[x])
		diff_weight[x] += diff_weight[table[x]] #親の更新に伴う 重みの更新
		table[x] = root	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def union(x,y,w):	#xとyを diff(x,y)=w で繋げる
	w = w - weight(y) + weight(x)
	x = find(x)
	y = find(y)

	if x == y:
		return

	if rank[x] < rank[y]:
		x,y = y,x
		w = -w

	table[y] = x
	diff_weight[y] = w

	if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y): #xとyか繋がっているか -> return bool
	if find(x) == find(y):
		return True
	else:
		return False

def weight(x):
	find(x)	#経路圧縮
	return diff_weight[x]

def diff(x,y): # weight(y)-weight(x)  (繋がってる前提)
	return (weight(y) - weight(x))


H,W = inpl()
N = int(input())
lines = defaultdict(set)

table = [i for i in range(W)]	#木の親 table[x] == x なら根
rank  = [1 for i in range(W)]	#木の長さ
diff_weight = [0 for i in range(W)]



for _ in range(N):
	y,x,a = inpl()
	x,y = x-1,y-1
	lines[y].add((x,a))

for y in range(H):
	for i,[x,c] in enumerate(lines[y]):
		if i == 0:
			bx,bc = x,c
			continue
		else:
			if check(x,bx):
				if diff(x,bx) != c-bc:
					print('No')
					sys.exit()
			else:
				if c > bc:
					union(x,bx,c-bc)
				else:
					union(bx,x,bc-c)
		bx,bc = x,c


MAX = [0]*W
for i in range(W):
	x = find(i)
	MAX[x] = max(MAX[x],diff_weight[i])


for y in range(H):
	for x,c in lines[y]:
		if c - MAX[x] < 0:
			print('No')
			sys.exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

def find(x):	#xの根を返す
	global table
	global diff_weight

	if table[x] == x:
		return x
	else:
		root = find(table[x])
		diff_weight[x] += diff_weight[table[x]] #親の更新に伴う 重みの更新
		table[x] = root	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def union(x,y,w):	#xとyを diff(x,y)=w で繋げる
	w = w - weight(y) + weight(x)
	x = find(x)
	y = find(y)

	if x == y:
		return

	if rank[x] < rank[y]:
		x,y = y,x
		w = -w

	table[y] = x
	diff_weight[y] = w

	if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y): #xとyか繋がっているか -> return bool
	if find(x) == find(y):
		return True
	else:
		return False

def weight(x):
	find(x)	#経路圧縮
	return diff_weight[x]

def diff(x,y): # weight(y)-weight(x)  (繋がってる前提)
	return (weight(y) - weight(x))


H,W = inpl()
N = int(input())
lines = defaultdict(set)

table = [i for i in range(W)]	#木の親 table[x] == x なら根
rank  = [1 for i in range(W)]	#木の長さ
diff_weight = [0 for i in range(W)]



for _ in range(N):
	y,x,a = inpl()
	x,y = x-1,y-1
	lines[y].add((x,a))

for y in range(H):
	for i,[x,c] in enumerate(lines[y]):
		if i == 0:
			bx,bc = x,c
			continue
		else:
			if check(x,bx):
				if diff(x,bx) != c-bc:
					print('No')
					sys.exit()
			else:
				if c > bc:
					union(x,bx,c-bc)
				else:
					union(bx,x,bc-c)
		bx,bc = x,c


MAX = max(diff_weight)

for y in range(H):
	for x,c in lines[y]:
		if c - (MAX - diff_weight[x]) < 0:
			print('No')
			sys.exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

def find(x):	#xの根を返す
	global table
	global diff_weight

	if table[x] == x:
		return x
	else:
		root = find(table[x])
		diff_weight[x] += diff_weight[table[x]] #親の更新に伴う 重みの更新
		table[x] = root	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def union(x,y,w):	#xとyを diff(x,y)=w で繋げる
	w = w - weight(y) + weight(x)
	x = find(x)
	y = find(y)

	if x == y:
		return

	if rank[x] < rank[y]:
		x,y = y,x
		w = -w

	table[y] = x
	diff_weight[y] = w

	if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y): #xとyか繋がっているか -> return bool
	if find(x) == find(y):
		return True
	else:
		return False

def weight(x):
	find(x)	#経路圧縮
	return diff_weight[x]

def diff(x,y): # weight(y)-weight(x)  (繋がってる前提)
	return (weight(y) - weight(x))


H,W = inpl()
N = int(input())
lines = defaultdict(set)

table = [i for i in range(W)]	#木の親 table[x] == x なら根
rank  = [1 for i in range(W)]	#木の長さ
diff_weight = [0 for i in range(W)]



for _ in range(N):
	y,x,a = inpl()
	x,y = x-1,y-1
	lines[y].add((x,a))

for y in range(H):
	for i,[x,c] in enumerate(lines[y]):
		if i == 0:
			bx,bc = x,c
			continue
		else:
			if check(x,bx):
				if diff(x,bx) != c-bc:
					print('NO')
					sys.exit()
			else:
				if c > bc:
					union(x,bx,c-bc)
				else:
					union(bx,x,bc-c)
		bx,bc = x,c


MAX = max(diff_weight)

for y in range(H):
	for x,c in lines[y]:
		if c - (MAX - diff_weight[x]) < 0:
			print('NO')
			sys.exit()

print('YES')

Submission status: Wrong Answer

Solution code:
R, C = map(int,input().split())
N = int(input())
INF = 10**10
row = [INF]*R
col = [INF]*C
row[0] = 0
col[0] = 0
rca = [[int(i) for i in input().split()] for j in range(N)]
rca.sort()
tl = 0
for i in range(N):
    r, c, a = rca[i]
    if(r == 1 and c == 1):
        tl = a

for i in range(N):
    r, c, a = rca[i]
    if(r == 1):
        col[c-1] = a - tl
    elif(c == 1):
        row[r-1] = a - tl


for i in range(N):
    r, c, a = rca[i]
    t = tl
    f = False
    g = False
    if(row[r-1] != INF):
        t += row[r-1]
        f = True
    if(col[c-1] != INF):
        t += col[c-1]
        g = True
    if(f and not g):
        col[c-1] = a - t
    elif(g and not f):
        row[r-1] = a - t
    elif(f and g):
        if(t != a):
            #print(r,c,a,row[r-1],col[c-1])
            print("No")
            break
    else:
        row[r-1] = a
        col[c-1] = 0
else:
    if(min([row[i] for i in range(R) if(row[i] != INF)])+min([col[i] for i in range(C) if(col[i] != INF)])+tl < 0):
        print("No")
    else:
        print("Yes")

Submission status: Wrong Answer

Solution code:
R, C = map(int,input().split())
N = int(input())
INF = 10**10
row = [INF]*R
col = [INF]*C
row[0] = 0
col[0] = 0
rca = [[int(i) for i in input().split()] for j in range(N)]
rca.sort()
tl = 0
for i in range(N):
    r, c, a = rca[i]
    if(r == 1 and c == 1):
        tl = a

for i in range(N):
    r, c, a = rca[i]
    if(r == 1):
        col[c-1] = a - tl
    elif(c == 1):
        row[r-1] = a - tl


for i in range(N):
    r, c, a = rca[i]
    t = tl
    f = False
    g = False
    if(row[r-1] != INF):
        t += row[r-1]
        f = True
    if(col[c-1] != INF):
        t += col[c-1]
        g = True
    if(f and not g):
        col[c-1] = a - t
    if(g and not f):
        row[r-1] = a - t
    if(f and g and t != a):
        #print(r,c,a,row[r-1],col[c-1])
        print("No")
        break
else:
    if(min([row[i] for i in range(R) if(row[i] != INF)])+min([col[i] for i in range(C) if(col[i] != INF)])+tl < 0):
        print("No")
    else:
        print("Yes")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
#-*- coding: utf-8 -*-
# E-LRU Puzle
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
#Data input
(N, M) = reads()
Q = int(input())
A = reads(1)

#Data structure initial
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N

#Pattern search & Match count
counter = 0
for i in A[::-1]:
	if (i not in pat):
		pat.append(i)
		pos[i] = counter
		freq[counter] -= 1
		counter += 1
		freq[counter] += 1
	else:
		temp = pos[i]
		if (freq[temp] > 0):
			freq[temp] -= 1
			freq[temp+1] += 1

if(counter != M):
	for i in range(M):
		if (i not in pat):
			pat.append(i)

#Result judge
for i in range(M):
	if (freq[i] != 0):
		start = i
		break

p = pat[start:]
p.sort()
if(p == pat[start:]):
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

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

R, C = map(int, input().split())
N = int(input())
r = []
c = []
a = []
for i in range(N):
    ri, ci, ai = map(int, input().split())
    r.append(ri)
    c.append(ci)
    a.append(ai)
x = {}
y = {}
     
for i in range(N):
    if r[i] in x:
        if c[i] in y:
            if x[r[i]] + y[c[i]] != a[i]:
                print("No")
                break
        else:
            y[c[i]] = a[i] - x[r[i]]
    else:
        if c[i] in y:
            x[r[i]] = a[i] - y[c[i]]
        else:
            x[r[i]] = a[i]
            y[c[i]] = 0

else:
    if min(y.values()) + min(x.values()) >= 0:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
R, C = map(int, input().split())
N = int(input())
r = []
c = []
a = []
for i in range(N):
	ri, ci, ai = map(int, input().split())
	r.append(ri)
	c.append(ci)
	a.append(ai)
x = {}
y = {}

for i in range(N):
	if r[i] in x:
		if c[i] in y:
			if x[r[i]] + y[c[i]] != a[i]:
				print("No")
				break
		else:
			y[c[i]] = a[i] - x[r[i]]
	else:
		if c[i] in y:
			x[r[i]] = a[i] - y[c[i]]
		else:
			x[r[i]] = a[i]
			y[c[i]] = 0

else:
	if min(y.values()) + min(x.values()) >= 0:
		print("Yes")
	else:
		print("No")

Submission status: Wrong Answer

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

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp is not VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) is not 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] is "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] is "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp is not VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) is not 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] is "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] is "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(('R', r))
	VectorSet.add(('C', c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				print("No equal")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		print("min")
		exit()
		
print("Yes")