結果

問題 No.1365 [Cherry 1st Tune] Whose Fault?
ユーザー chineristAC
提出日時 2021-01-22 23:05:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 568 ms / 2,000 ms
コード長 913 bytes
コンパイル時間 596 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 127,664 KB
最終ジャッジ日時 2024-12-29 09:53:59
合計ジャッジ時間 16,161 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
P = list(map(int,input().split()))

S = [A[i]-B[i] for i in range(N)]
for i in range(N):
    if P[i]:
        P[i] = 1/P[i]
    else:
        P[i] = float("inf")

ans = 0
for i in range(N):
    ans += S[i]**2 / P[i]

parent = [i for i in range(N)]
g = [set([i]) for i in range(N)]

def unite(x,y):
    global ans
    if parent[x]==parent[y]:
        return

    gx,gy = parent[x],parent[y]
    if len(g[gy]) > len(g[gx]):
        gx,gy = gy,gx

    ans -= S[gx]**2 / P[gx]
    ans -= S[gy]**2 / P[gy]

    S[gx] += S[gy]
    P[gx] += P[gy]

    ans += S[gx]**2 / P[gx]

    for v in g[gy]:
        parent[v] = gx
        g[gx].add(v)

    g[gy] = []


res = []
for _ in range(int(input())):
    x,y = map(int,input().split())
    unite(x-1,y-1)
    res.append(ans)

print(*res,sep="\n")
0