Submission #67338392

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 bisect import bisect_left
from collections import deque, defaultdict
def solve():
    H,W,K=map(int, input().split())
    A=[list(map(int, input().split())) for _ in range(K)]
    R=defaultdict(list)
    C=defaultdict(list)
    for r,c in A:
        R[r].append(c)
        C[c].append(r)
    for i in range(1,H+1):
        R[i].extend([0,W+1])
        R[i].sort()
    for j in range(1,W+1):
        C[j].extend([0,H+1])
        C[j].sort()
        
    rr={j: set(range(1,H+1))-set(C[j]) for j in C}
    rc={i: set(range(1,W+1))-set(R[i]) for i in R}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from bisect import bisect_left
from collections import deque, defaultdict

def solve():
    H,W,K=map(int, input().split())
    A=[list(map(int, input().split())) for _ in range(K)]

    R=defaultdict(list)
    C=defaultdict(list)
    for r,c in A:
        R[r].append(c)
        C[c].append(r)
    for i in range(1,H+1):
        R[i].extend([0,W+1])
        R[i].sort()
    for j in range(1,W+1):
        C[j].extend([0,H+1])
        C[j].sort()
        
    rr={j: set(range(1,H+1))-set(C[j]) for j in C}
    rc={i: set(range(1,W+1))-set(R[i]) for i in R}
    
    Q=deque()
    if (1 not in rr.get(1,set())) or (1 not in rc.get(1,set())):
        print("No")
        return
    
    Q.append((1,1))
    rc[1].discard(1)
    rr[1].discard(1)

    while Q:
        i,j=Q.popleft()
        if (i,j)==(H,W):
            print("Yes")
            return


        B=R[i]
        idx=bisect_left(B,j)
        l=B[idx-1]+1
        r=B[idx]-1
        cand=[c for c in rc[i] if l<=c<=r]
        for c in cand:
            rc[i].discard(c)
            rr[c].discard(i)
            Q.append((i,c))

        B=C[j]
        idx=bisect_left(B,i)
        l=B[idx-1]+1
        r=B[idx]-1
        cand=[c for c in rr[j] if l<=c<=r]
        for c in cand:
            rr[j].discard(c)
            rc[r].discard(j)
            Q.append((c,j))

    print("No")

solve()

Submission Info

Judge Result