結果

問題 No.3720 Balanced Reduction
コンテスト
ユーザー kidodesu
提出日時 2026-09-18 23:08:26
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 3,850 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 75 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 443,628 KB
最終ジャッジ日時 2026-09-18 23:08:38
合計ジャッジ時間 7,809 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10 WA * 5 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from bisect import bisect as bs
def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, input().split()))
    node = [[] for _ in range(n)]
    E = [0] * n
    for _ in range(n):
        u, v = list(map(lambda x: int(x)-1, input().split()))
        node[u].append(v)
        node[v].append(u)
        E[u] += 1
        E[v] += 1
    S = [u for u in range(n) if E[u] == 1]
    ans0 = 0
    K = [k]
    t = 2*k
    while t <= 10**9:
        K.append(t+1)
        t *= 2
    while S:
        u = S.pop()
        if A[u] == 0:
            pass
        elif A[u] < k:
            return -1
        ans0 += bs(K, A[u])
        for v in node[u]:
            if E[v]:
                E[v] -= 1
                E[u] -= 1
                A[v] -= A[u]
                A[u] = 0
                if E[v] == 1:
                    S.append(v)
    X = set()
    u = 0
    while not E[u]:
        u += 1
    B = []
    while 1:
        X.add(u)
        B.append(A[u])
        for v in node[u]:
            if not v in X and E[v]:
                u = v
                break
        else:
            break
    ans1 = 0
    N = len(B)
    A = B
    if N % 2:
        t0 = t1 = 0
        for u in range(N):
            if not u % 2:
                t0 += A[u]
            else:
                t1 += A[u]
        if (t0-t1) % 2: return -1
        x = (t0 - t1) // 2
        if x < 0: return -1
        elif 0 < x < k: return -1
        ans1 += bs(K, x)
        A[0] -= x
        A[-1] -= x
        for i in range(N-1):
            if A[i] < 0 or 0 < A[i] < k: return -1
            ans1 += bs(K, A[i])
            A[i+1] -= A[i]
    else:
        t0 = t1 = 0
        for u in range(N):
            if not u % 2:
                t0 += A[u]
            else:
                t1 += A[u]
        if t0 != t1: return -1
        X0 = []
        X1 = [0]
        for u in range(N-1):
            if not u % 2:
                X0.append(A[u])
            else:
                X1.append(A[u])
            A[u+1] -= A[u]
            A[u] = 0
        X0.sort()
        X1.sort()
        xx = -X1[0]
        X0 = [x0-xx for x0 in X0]
        X1 = [x1+xx for x1 in X1]
        #print(X0, X1)
        inf = 1<<60
        ans1 = inf
        ans2 = ans3 = 0
        for x in X0:
            if x < 0 or 0 < x < k:
                break
            else:
                ans2 += bs(K, x)
        else:
            for x in X1:
                if x < 0 or 0 < x < k:
                    break
                else:
                    ans2 += bs(K, x)
            else:
                ans1 = min(ans1, ans2)
        for x in X0:
            x -= X0[0]
            if x < 0 or 0 < x < k:
                break
            else:
                ans3 += bs(K, x)
        else:
            for x in X1:
                x += X0[0]
                if x < 0 or 0 < x < k:
                    break
                else:
                    ans3 += bs(K, x)
            else:
                ans1 = min(ans1, ans3)
        X0 = [x0-k for x0 in X0]
        X1 = [x1+k for x1 in X1]
        r = X0[0]-k
        t = 0
        if r < 0:
            pass
        else:
            for x in X0+X1:
                if x < 0 or 0 < x < k:
                    t += inf
                else:
                    t += bs(K, x)
            F = []
            for x in X0:
                for ki in K:
                    ki -= 1
                    if ki < x and x-ki <= r:
                        F.append((x-ki, -1))
            for x in X1:
                for ki in K:
                    if x < ki and ki-x <= r:
                        F.append((x-ki, 1))
            ans1 = min(ans1, t)
            F.sort()
            for _, s in F:
                t += s
                ans1 = min(ans1, t)
        if 1<<59 <= ans1:
            return -1
    return ans0+ans1

print(main())
0