結果

問題 No.2311 [Cherry 5th Tune] Cherry Month
コンテスト
ユーザー 👑 Kazun
提出日時 2023-01-05 01:07:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,948 ms / 4,600 ms
コード長 2,936 bytes
コンパイル時間 843 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 228,956 KB
最終ジャッジ日時 2024-12-15 19:04:38
合計ジャッジ時間 63,701 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def solve():
    #==================================================
    # 関数パート
    def find(x):
        P=[]
        while UF[x]!=x:
            P.append(x)
            x=UF[x]

        for y in P:
            UF[y]=x
        return x

    def add_edge(x,y):
        xc=find(x); yc=find(y)

        G[x].append(y)
        G[y].append(x)

        if is_large(x):
            large_nei[y].append(x)
        if is_large(y):
            large_nei[x].append(y)

        Fall[xc][x]-=Delay[y]
        Fall[yc][y]-=Delay[x]

        if xc==yc:
            return False

        if len(Fall[xc])<len(Fall[yc]):
            xc,yc=yc,xc

        UF[yc]=xc
        delta=Comp[xc]-Comp[yc]
        Comp[yc]=0
        for z in Fall[yc]:
            Fall[xc][z]=Fall[yc][z]-delta
        Fall[yc].clear()

        return True

    def is_large(i):
        return deg[i]>=B

    def fall_petal_individual(i,k):
        Fall[find(i)][i]+=k

    def get_petal(i):
        petal=A[i]-(Fall[find(i)][i]+Comp[find(i)])
        for j in large_nei[i]:
            petal-=Delay[j]
        return max(0,petal)
    #==================================================
    from math import sqrt, ceil

    #==================================================
    # 入力パート
    N=int(input())
    A=[0]+list(map(int,input().split()))

    deg=[1]*(N+1); size=N+1
    T=int(input())
    F=[0]*(T+1); X=[0]*(T+1); Y=[0]*(T+1)
    for t in range(1,T+1):
        F[t],X[t],Y[t]=tuple(map(int,input().split()))

        if F[t]==1:
            deg[X[t]]+=1
            deg[Y[t]]+=1
            size+=1

    Q=int(input())
    Question=[[] for _ in range(T+1)]
    for q in range(Q):
        S,I=map(int,input().split())
        Question[S].append((q,I))

    #==================================================
    # 前計算パート

    B=ceil(sqrt(size))
    large_nei=[[i] if is_large(i) else [] for i in range(N+1)]

    UF=list(range(N+1))
    Fall=[{i:0} for i in range(N+1)]
    Delay=[0]*(N+1)
    Comp=[0]*(N+1)

    G=[[i] for i in range(N+1)]

    #==================================================
    # 本計算パート

    Ans=[0]*Q
    for t in range(T+1):
        if F[t]==1:
            add_edge(X[t],Y[t])
        elif F[t]==2:
            x=X[t]; k=Y[t]
            fall_petal_individual(x,k)
        elif F[t]==3:
            x=X[t]; k=Y[t]
            if is_large(x):
                Delay[x]+=k
            else:
                for y in G[x]:
                    fall_petal_individual(y,k)
        elif F[t]==4:
            x=X[t]; k=Y[t]
            Comp[find(x)]+=k

        for q,I in Question[t]:
            Ans[q]=get_petal(I)

    return Ans

#==================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write

write("\n".join(map(str,solve())))
0