Submission #67345111

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import defaultdict
class dsu():
    n = 1
    parent_or_size = []
    def __init__(self, N):
        self.n = N
        self.parent_or_size = [-1 for _ in range(N)]
    def merge(self, a, b):
        assert 0 <= a < self.n and 0 <= b < self.n
        x = self.leader(a)
        y = self.leader(b)
        if x == y:
            return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x
    def same(self, a, b):
        return self.leader(a) == self.leader(b)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import defaultdict

class dsu():
    n = 1
    parent_or_size = []
    def __init__(self, N):
        self.n = N
        self.parent_or_size = [-1 for _ in range(N)]
    def merge(self, a, b):
        assert 0 <= a < self.n and 0 <= b < self.n
        x = self.leader(a)
        y = self.leader(b)
        if x == y:
            return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x
    def same(self, a, b):
        return self.leader(a) == self.leader(b)
    def leader(self, a):
        if self.parent_or_size[a] < 0:
            return a
        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]
    def size(self, a):
        return -self.parent_or_size[self.leader(a)]
    def groups(self):
        leader_buf = [self.leader(i) for i in range(self.n)]
        groups = defaultdict(list)
        for i, p in enumerate(leader_buf):
            groups[p].append(i)
        return list(groups.values())

H,W,K=map(int, input().split())
A=[tuple(map(int, input().split())) for _ in range(K)]

uf=dsu(K)

rmin=[r for r, c in A]
rmax=[r for r, c in A]
cmin=[c for r, c in A]
cmax=[c for r, c in A]

idx={A[i]: i for i in range(K)}

dirs=[(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]
for i,(r, c) in enumerate(A):
    for dr,dc in dirs:
        nbr = (r + dr, c + dc)
        if nbr in idx:
            j=idx[nbr]
            ri=uf.leader(i)
            rj=uf.leader(j)
            
            if ri!=rj:
                new=uf.merge(ri, rj)
                pre1,pre2=(rmin[ri], rmax[ri], cmin[ri], cmax[ri]), (rmin[rj], rmax[rj], cmin[rj], cmax[rj])
                
                rmin[new] = min(pre1[0],pre2[0])
                rmax[new] = max(pre1[1],pre2[1])
                cmin[new] = min(pre1[2],pre2[2])
                cmax[new] = max(pre1[3],pre2[3])


for i in range(K):
    if uf.leader(i)!=i:
        continue

    if cmin[i] == 1 and cmax[i] == W:
        print("No")
        break
    if rmin[i] == 1 and rmax[i] == H:
        print("No")
        break
else:
    print("Yes")

Submission Info

Judge Result