結果

問題 No.2786 RMQ on Grid Path
ユーザー liupengsayliupengsay
提出日時 2024-06-15 16:03:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,767 ms / 6,000 ms
コード長 6,564 bytes
コンパイル時間 401 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 181,888 KB
最終ジャッジ日時 2024-06-15 16:04:15
合計ジャッジ時間 36,725 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
56,108 KB
testcase_01 AC 47 ms
56,948 KB
testcase_02 AC 73 ms
73,500 KB
testcase_03 AC 73 ms
72,920 KB
testcase_04 AC 80 ms
76,564 KB
testcase_05 AC 73 ms
74,260 KB
testcase_06 AC 73 ms
74,272 KB
testcase_07 AC 73 ms
74,232 KB
testcase_08 AC 70 ms
72,932 KB
testcase_09 AC 74 ms
74,632 KB
testcase_10 AC 67 ms
72,240 KB
testcase_11 AC 71 ms
73,980 KB
testcase_12 AC 1,739 ms
181,888 KB
testcase_13 AC 1,726 ms
179,516 KB
testcase_14 AC 1,751 ms
181,508 KB
testcase_15 AC 1,767 ms
180,764 KB
testcase_16 AC 1,720 ms
179,968 KB
testcase_17 AC 1,735 ms
181,716 KB
testcase_18 AC 1,641 ms
163,532 KB
testcase_19 AC 1,760 ms
179,964 KB
testcase_20 AC 1,766 ms
180,860 KB
testcase_21 AC 1,615 ms
164,180 KB
testcase_22 AC 1,129 ms
150,872 KB
testcase_23 AC 1,120 ms
150,332 KB
testcase_24 AC 1,267 ms
145,872 KB
testcase_25 AC 1,203 ms
146,760 KB
testcase_26 AC 1,214 ms
146,620 KB
testcase_27 AC 674 ms
124,232 KB
testcase_28 AC 599 ms
137,156 KB
testcase_29 AC 1,327 ms
148,104 KB
testcase_30 AC 586 ms
125,152 KB
testcase_31 AC 228 ms
82,784 KB
testcase_32 AC 1,192 ms
151,772 KB
testcase_33 AC 287 ms
115,868 KB
testcase_34 AC 1,035 ms
135,872 KB
testcase_35 AC 1,053 ms
150,680 KB
testcase_36 AC 1,062 ms
151,984 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
from sys import stdin


class FastIO:
    def __init__(self):
        self.random_seed = 0
        self.flush = False
        self.inf = 1 << 32
        return

    @staticmethod
    def read_int():
        return int(stdin.readline().rstrip())

    @staticmethod
    def read_float():
        return float(stdin.readline().rstrip())

    @staticmethod
    def read_list_ints():
        return list(map(int, stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_ints_minus_one():
        return list(map(lambda x: int(x) - 1, stdin.readline().rstrip().split()))

    @staticmethod
    def read_str():
        return stdin.readline().rstrip()

    @staticmethod
    def read_list_strs():
        return stdin.readline().rstrip().split()

    def get_random_seed(self):
        import random
        self.random_seed = random.randint(0, 10 ** 9 + 7)
        return

    def st(self, x):
        return print(x, flush=self.flush)

    def yes(self, s=None):
        self.st("Yes" if not s else s)
        return

    def no(self, s=None):
        self.st("No" if not s else s)
        return

    def lst(self, x):
        return print(*x, flush=self.flush)

    def flatten(self, lst):
        self.st("\n".join(str(x) for x in lst))
        return

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def ceil(a, b):
        return a // b + int(a % b != 0)

    @staticmethod
    def accumulate(nums):
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]
        return pre


class UnionFind:
    def __init__(self, n: int) -> None:
        self.root_or_size = [-1] * n
        self.part = n
        self.n = n
        return

    def initialize(self):
        for i in range(self.n):
            self.root_or_size[i] = -1
        self.part = self.n
        return

    def find(self, x):
        y = x
        while self.root_or_size[x] >= 0:
            # range_merge_to_disjoint to the direct root node after query
            x = self.root_or_size[x]
        while y != x:
            self.root_or_size[y], y = x, self.root_or_size[y]
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.root_or_size[root_x] < self.root_or_size[root_y]:
            root_x, root_y = root_y, root_x
        self.root_or_size[root_y] += self.root_or_size[root_x]
        self.root_or_size[root_x] = root_y
        self.part -= 1
        return True

    def union_left(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        self.root_or_size[root_x] += self.root_or_size[root_y]
        self.root_or_size[root_y] = root_x
        self.part -= 1
        return True

    def union_right(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        self.root_or_size[root_y] += self.root_or_size[root_x]
        self.root_or_size[root_x] = root_y
        self.part -= 1
        return True

    def union_max(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if root_x > root_y:
            root_x, root_y = root_y, root_x
        self.root_or_size[root_y] += self.root_or_size[root_x]
        self.root_or_size[root_x] = root_y
        self.part -= 1
        return

    def union_min(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if root_x < root_y:
            root_x, root_y = root_y, root_x
        self.root_or_size[root_y] += self.root_or_size[root_x]
        self.root_or_size[root_x] = root_y
        self.part -= 1
        return

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.root_or_size[self.find(x)]

    def get_root_part(self):
        # get the nodes list of every root
        part = defaultdict(list)
        n = len(self.root_or_size)
        for i in range(n):
            part[self.find(i)].append(i)
        return part

    def get_root_size(self):
        # get the size of every root
        size = defaultdict(int)
        n = len(self.root_or_size)
        for i in range(n):
            if self.find(i) == i:
                size[i] = -self.root_or_size[i]
        return size


class Solution:
    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        """
        url: url of the problem
        tag: algorithm tag
        """
        m, n = ac.read_list_ints()
        grid = [ac.read_list_ints() for _ in range(m)]
        q = ac.read_int()
        ans = [-1] * q
        dct = [[] for _ in range(m * n)]
        for i in range(q):
            x1, y1, x2, y2 = ac.read_list_ints_minus_one()
            dct[x1 * n + y1].append((i, x2 * n + y2))
            dct[x2 * n + y2].append((i, x1 * n + y1))
        ind = list(range(m * n))
        ind.sort(key=lambda it: grid[it // n][it % n])
        uf = UnionFind(m * n)
        for num in ind:
            x, y = num // n, num % n
            for a, b in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= a < m and 0 <= b < n and grid[a][b] <= grid[x][y] and not uf.is_connected(num, a * n + b):
                    root1, root2 = uf.find(num), uf.find(a * n + b)
                    if len(dct[root1]) < len(dct[root2]):
                        lst = []
                        for i, xx in dct[root1]:
                            if uf.is_connected(xx, root2):
                                ans[i] = grid[x][y]
                            else:
                                lst.append((i, xx))
                        dct[root2].extend(lst)
                        uf.union_left(root2, root1)
                    else:
                        lst = []
                        for i, xx in dct[root2]:
                            if uf.is_connected(xx, root1):
                                ans[i] = grid[x][y]
                            else:
                                lst.append((i, xx))
                        dct[root1].extend(lst)
                        uf.union_left(root1, root2)
        for a in ans:
            ac.st(a)

        return


Solution().main()
0