結果

問題 No.3351 Towering Tower
コンテスト
ユーザー tassei903
提出日時 2025-11-10 02:33:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,340 bytes
コンパイル時間 348 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 92,944 KB
最終ジャッジ日時 2025-11-13 21:13:19
合計ジャッジ時間 11,431 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other WA * 3 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve(n, g, h):
    inf = -10 ** 18
    h.append(-1)

    def check(x):
        L = [[inf, inf] for _ in range(n + 1)]
        R = [[-inf, -inf] for _ in range(n + 1)]
        # L[i][0] <= t[i] <= R[i][0] に対して、
        # 2 * t[i]  
        # L[i][1] <= t[i] <= R[i][1] に対して、
        # 2 * t[i] + 1 の時刻に到達可能
        h[n] = x
        for i in g[n]:
            L[i][1] = 0
            R[i][1] = 0

        for time in range(n * 2):
            for u in range(n + 1):
                for v in g[u]:
                    if h[u] == h[v]:
                        if h[u] <= x:
                            for t in range(2):
                                L[v][t^1] = min(L[v][t^1], L[u][t] + t)
                                R[v][t^1] = max(R[v][t^1], R[u][t] + t)
                    elif h[u] > h[v]:
                        Y = (x - h[u]) // (h[u] - h[v])
                        # 2s + t <= Y
                        # min(R[v][t], (Y - t) // 2)
                        for t in range(2):
                            y = (Y - t) // 2
                            L[v][t^1] = min(L[v][t^1], L[u][t] + t)
                            R[v][t^1] = max(R[v][t^1], min(R[u][t] + t, y))
                    else:
                        Y = (x - h[u] - 1) // (h[u] - h[v]) + 1
                        # 2s + t >= Y
                        # max(L[v][t], (Y - t + 1) // 2
                        for t in range(2):
                            y = (Y - t + 1) // 2
                            L[v][t^1] = min(L[v][t^1], max(L[u][t] + t, y))
                            R[v][t^1] = max(R[v][t^1], R[u][t] + t)
            # print(time)
            # print(L)
            # print(R)

        return all(L[i][0] <= R[i][0] or L[i][1] <= R[i][1] for i in range(n))



    ok = 10 ** 13
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        res = check(mid)
        # print(mid, res)
        # print()
        if res:
            ok = mid
        else:
            ng = mid
    return ok

for _ in range(int(input())):
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    g = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append(v)
        g[v].append(u)
    print(solve(n, g, h))
0