#1187415 (PyPy3) No.3720 Balanced Reduction

• 問題: No.3720 Balanced Reduction
• ユーザー: 👑 loop0919
• 提出日時: 2026-09-18 18:44:51
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 710 ms / 2,000 ms
• コード長: 3,641 bytes
• コンパイル時間: 73 ms
• コンパイル使用メモリ: 81,920 KB
• 実行使用メモリ: 141,888 KB
• 最終ジャッジ日時: 2026-09-18 20:52:03
• 合計ジャッジ時間: 5,927 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 4
other	AC * 16

ソースコード

from collections import deque


def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    graph = [[] for _ in range(N)]
    for _ in range(N):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)

    M = 2 * K
    INF = 10**30

    # 木の部分を葉から取り除く。
    degree = [len(adj) for adj in graph]
    que = deque(v for v in range(N) if degree[v] == 1)
    fixed = 0

    while que:
        v = que.popleft()
        w = A[v]

        if w < 0 or 0 < w < K:
            return -1

        fixed += (w + M - 1) // M
        degree[v] = 0

        for u in graph[v]:
            if degree[u] > 0:
                A[u] -= w
                if A[u] < 0:
                    return -1

                degree[u] -= 1
                if degree[u] == 1:
                    que.append(u)
                break

    # 残ったサイクルの頂点を順番に並べる。
    start = next(v for v in range(N) if degree[v] > 0)
    B = []
    prev, v = -1, start

    while True:
        B.append(A[v])

        for u in graph[v]:
            if degree[u] > 0 and u != prev:
                nxt = u
                break

        prev, v = v, nxt
        if v == start:
            break

    m = len(B)

    # サイクルの辺 i の総量は (-1)^i * t + C[i]。
    C = [0] * m
    for i in range(1, m):
        C[i] = B[i] - C[i - 1]

    def cycle_cost(t):
        result = 0
        for i, c in enumerate(C):
            w = c + t if i % 2 == 0 else c - t
            if w < 0 or 0 < w < K:
                return INF
            result += (w + M - 1) // M
        return result

    # 奇数長なら t が一意に決まる。
    if m % 2 == 1:
        numerator = B[0] - C[-1]
        if numerator % 2 != 0:
            return -1

        value = cycle_cost(numerator // 2)
        return -1 if value == INF else fixed + value

    # 偶数長では、まず最後の頂点の条件を確認する。
    if C[-1] != B[0]:
        return -1

    L = max(-C[i] for i in range(0, m, 2))
    R = min(C[i] for i in range(1, m, 2))
    if L > R:
        return -1

    # 両端は、総量が 1 以上 K 未満の辺がないか個別に調べる。
    best = min(cycle_cost(L), cycle_cost(R))

    # 中央の区間では全辺の総量が K 以上になる。
    lo, hi = L + K, R - K
    if lo <= hi:
        # 周期 M のうち、最大 M 個の整数だけを調べればよい。
        span = min(hi - lo, M - 1)
        events = []
        current = 0

        for i, c in enumerate(C):
            w = c + lo if i % 2 == 0 else c - lo
            count = (w + M - 1) // M
            current += count

            if i % 2 == 0:
                # 総量が count * M + 1 になると操作回数が 1 増える。
                d = count * M + 1 - w
                change = 1
            else:
                # 総量が (count - 1) * M になると操作回数が 1 減る。
                d = w - (count - 1) * M
                change = -1

            if d <= span:
                events.append((d, change))

        best = min(best, current)
        events.sort()

        # 同じ位置で起こる変化はすべて反映してから最小値を更新する。
        i = 0
        while i < len(events):
            d = events[i][0]
            while i < len(events) and events[i][0] == d:
                current += events[i][1]
                i += 1
            best = min(best, current)

    return -1 if best == INF else fixed + best


if __name__ == "__main__":
    print(solve())