結果

問題 No.3351 Towering Tower
コンテスト
ユーザー Nzt3
提出日時 2025-11-11 00:25:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,421 ms / 3,000 ms
コード長 3,165 bytes
コンパイル時間 319 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 90,628 KB
最終ジャッジ日時 2025-11-13 21:16:24
合計ジャッジ時間 30,289 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

input = sys.stdin.readline
INF = (1 << 61) + (1 << 31) - 1

def solve():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    H.append(0)  # H[N] will be overwritten in loop

    G = [[] for _ in range(N + 1)]
    for _ in range(M):
        U, V = map(int, input().split())
        U -= 1
        V -= 1
        if V != N:
            G[U].append(V)
        G[V].append(U)

    Hord = sorted([(H[i], i) for i in range(N)])
    ans = 10**9 * N
    ng = -1

    def nminmax(fr, to, X):
        if fr == N:
            return (-100, INF)
        if H[to] == H[fr]:
            if H[fr] <= X:
                return (-100, INF)
            else:
                return (INF, -100)
        elif H[to] > H[fr]:
            if H[fr] <= X:
                return (-100, INF)
            else:
                return ((H[fr] - X + (H[to] - H[fr] - 1)) // (H[to] - H[fr]), INF)
        else:
            if H[fr] < X:
                return (-100, (H[fr] - X) // (H[to] - H[fr]))
            else:
                return (0, -100)

    while ans - ng > 1:
        mid = (ans + ng) // 2
        H[N] = mid

        dist = [-1] * ((N + 1) * 2)
        bfs = deque([N])
        dist[N] = 0

        while bfs:
            vs = bfs.popleft()
            v = vs % (N + 1)
            c = vs // (N + 1)
            for to0 in G[v]:
                to = to0 + (1 - c) * (N + 1)
                nl, nr = nminmax(v, to0, mid)
                if nl <= dist[vs] <= nr and dist[to] == -1:
                    dist[to] = dist[vs] + 1
                    bfs.append(to)

        mdist = dist[:]
        for vs in range((N + 1) * 2):
            if mdist[vs] == -1:
                continue
            if vs % (N + 1) == N:
                continue
            v = vs % (N + 1)
            c = vs // (N + 1)
            for to0 in G[v]:
                to = to0 + (1 - c) * (N + 1)
                nl, nr = nminmax(v, to0, mid)
                if nr >= dist[vs] >= nl and H[to0] <= H[v]:
                    if c:
                        mdist[vs] = max(mdist[vs], nr - 1 + nr % 2 + 2)
                        mdist[to] = max(mdist[to], nr - 1 + nr % 2 + 1)
                    else:
                        mdist[vs] = max(mdist[vs], nr - nr % 2 + 2)
                        mdist[to] = max(mdist[to], nr - nr % 2 + 1)

        mdist = [min(x, INF) if x >= 0 else x for x in mdist]

        for h, v in Hord:
            for c in range(2):
                vs = v + c * (N + 1)
                if mdist[vs] < 0:
                    continue
                for to0 in G[v]:
                    to = to0 + (1 - c) * (N + 1)
                    nl, nr = nminmax(v, to0, mid)
                    if nl <= mdist[vs] <= nr:
                        mdist[to] = max(mdist[to], mdist[vs] + 1)
                        mdist[to] = min(mdist[to], INF)

        ok = True
        for i in range(N):
            if mdist[i] == -1 and mdist[i + (N + 1)] == -1:
                ok = False

        if ok:
            ans = mid
        else:
            ng = mid

    print(ans)

# main
T = int(input())
for _ in range(T):
    solve()
0