結果

問題 No.2786 RMQ on Grid Path
ユーザー lam6er
提出日時 2025-03-26 15:44:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 4,317 ms / 6,000 ms
コード長 3,438 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 326,252 KB
最終ジャッジ日時 2025-03-26 15:45:45
合計ジャッジ時間 76,769 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    ptr = 0
    H = int(input[ptr])
    ptr += 1
    W = int(input[ptr])
    ptr += 1

    A = []
    for _ in range(H):
        row = list(map(int, input[ptr:ptr+W]))
        ptr += W
        A.append(row)
    
    edges = []
    for i in range(H):
        for j in range(W):
            current = i * W + j
            if j < W - 1:
                right = i * W + (j + 1)
                w = max(A[i][j], A[i][j+1])
                edges.append((w, current, right))
            if i < H - 1:
                down = (i + 1) * W + j
                w = max(A[i][j], A[i+1][j])
                edges.append((w, current, down))
    
    edges.sort()
    size = H * W
    parent_uf = list(range(size))
    rank = [1] * size

    def find(u):
        if parent_uf[u] != u:
            parent_uf[u] = find(parent_uf[u])
        return parent_uf[u]

    mst_edges = [[] for _ in range(size)]
    for w, u, v in edges:
        root_u = find(u)
        root_v = find(v)
        if root_u != root_v:
            if rank[root_u] > rank[root_v]:
                parent_uf[root_v] = root_u
            else:
                parent_uf[root_u] = root_v
                if rank[root_u] == rank[root_v]:
                    rank[root_v] += 1
            mst_edges[u].append((v, w))
            mst_edges[v].append((u, w))
    
    log_max = 20
    depth = [0] * size
    parent = [-1] * size
    max_from_parent = [0] * size
    root = 0
    queue = deque([root])
    parent[root] = -1

    while queue:
        u = queue.popleft()
        for v, w in mst_edges[u]:
            if parent[v] == -1 and v != root:
                parent[v] = u
                max_from_parent[v] = w
                depth[v] = depth[u] + 1
                queue.append(v)
    
    up = [[-1] * size for _ in range(log_max)]
    max_edge = [[0] * size for _ in range(log_max)]
    for u in range(size):
        up[0][u] = parent[u]
        max_edge[0][u] = max_from_parent[u]
    
    for k in range(1, log_max):
        for u in range(size):
            if up[k-1][u] != -1:
                up[k][u] = up[k-1][up[k-1][u]]
                max_edge[k][u] = max(max_edge[k-1][u], max_edge[k-1][up[k-1][u]])
            else:
                up[k][u] = -1
                max_edge[k][u] = max_edge[k-1][u]
    
    Q = int(input[ptr])
    ptr += 1
    for _ in range(Q):
        rs = int(input[ptr])
        ptr += 1
        cs = int(input[ptr])
        ptr += 1
        rt = int(input[ptr])
        ptr += 1
        ct = int(input[ptr])
        ptr += 1
        u = (rs - 1) * W + (cs - 1)
        v = (rt - 1) * W + (ct - 1)
        
        res = 0
        du = depth[u]
        dv = depth[v]
        u_orig = u
        v_orig = v

        if depth[u] < depth[v]:
            u, v = v, u
        
        for k in range(log_max-1, -1, -1):
            if up[k][u] != -1 and depth[up[k][u]] >= depth[v]:
                res = max(res, max_edge[k][u])
                u = up[k][u]
        
        if u == v:
            print(res)
            continue
        
        for k in range(log_max-1, -1, -1):
            if up[k][u] != up[k][v]:
                res = max(res, max_edge[k][u], max_edge[k][v])
                u = up[k][u]
                v = up[k][v]
        
        res = max(res, max_edge[0][u], max_edge[0][v])
        print(res)

if __name__ == "__main__":
    main()
0