提出 #25857657

---

ソースコード 拡げる

# -*- coding: utf-8 -*-
"""
012 - Red Painting（★4）
https://atcoder.jp/contests/typical90/tasks/typical90_l

"""
import sys


class DisjointSet(object):
    def __init__(self, n):
        self.rank = [0] * n
        self.p = list(range(n))
        self.size = [1] * n

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.size[self.p[x]] += self.size[self.p[y]]
            self.p[y] = self.findSet(x)
        else:
            self.size[self.p[y]] += self.size[self.p[x]]
            self.p[x] = self.findSet(y)
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


def solve(H, W):
    d = DisjointSet(H * W)
    Q = int(input())
    reds = set()
    for _ in range(Q):
        cmd, *others = input().split()
        if cmd == '1':
            r, c = map(int, others)
            r, c, = r-1, c-1
            reds.add((r, c))
            for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                if (nr, nc) in reds:
                    d.unite(r*W+c, nr*W+nc)
        else:
            ra, ca, rb, cb = map(int, others)
            ra, ca, rb, cb = ra-1, ca-1, rb-1, cb-1
            res = d.same(ra*W+ca, rb*W+cb) if (ra, ca) in reds and (rb, cb) in reds else False
            print('Yes' if res else 'No')


def main(args):
    H, W = map(int, input().split())
    solve(H, W)


if __name__ == '__main__':
    main(sys.argv[1:])

提出情報

ジャッジ結果