結果

問題 No.2311 [Cherry 5th Tune] Cherry Month
ユーザー 👑 KazunKazun
提出日時 2023-01-05 01:07:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,691 ms / 4,600 ms
コード長 2,936 bytes
コンパイル時間 722 ms
コンパイル使用メモリ 87,232 KB
実行使用メモリ 231,652 KB
最終ジャッジ日時 2023-08-22 02:06:08
合計ジャッジ時間 62,613 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
71,520 KB
testcase_01 AC 71 ms
71,564 KB
testcase_02 AC 1,395 ms
193,876 KB
testcase_03 AC 548 ms
122,376 KB
testcase_04 AC 706 ms
114,716 KB
testcase_05 AC 668 ms
112,168 KB
testcase_06 AC 913 ms
122,268 KB
testcase_07 AC 615 ms
113,780 KB
testcase_08 AC 1,093 ms
177,716 KB
testcase_09 AC 944 ms
146,012 KB
testcase_10 AC 981 ms
151,736 KB
testcase_11 AC 1,008 ms
161,928 KB
testcase_12 AC 1,217 ms
169,432 KB
testcase_13 AC 1,056 ms
162,188 KB
testcase_14 AC 1,179 ms
171,804 KB
testcase_15 AC 1,146 ms
172,224 KB
testcase_16 AC 660 ms
110,204 KB
testcase_17 AC 1,317 ms
179,788 KB
testcase_18 AC 1,341 ms
172,032 KB
testcase_19 AC 1,135 ms
172,688 KB
testcase_20 AC 986 ms
164,196 KB
testcase_21 AC 1,038 ms
138,676 KB
testcase_22 AC 995 ms
142,200 KB
testcase_23 AC 902 ms
169,940 KB
testcase_24 AC 1,023 ms
167,328 KB
testcase_25 AC 944 ms
147,616 KB
testcase_26 AC 1,335 ms
182,916 KB
testcase_27 AC 993 ms
227,936 KB
testcase_28 AC 1,023 ms
231,428 KB
testcase_29 AC 987 ms
231,652 KB
testcase_30 AC 620 ms
142,100 KB
testcase_31 AC 630 ms
142,140 KB
testcase_32 AC 626 ms
142,176 KB
testcase_33 AC 1,010 ms
211,912 KB
testcase_34 AC 918 ms
208,632 KB
testcase_35 AC 999 ms
210,616 KB
testcase_36 AC 1,471 ms
217,640 KB
testcase_37 AC 1,549 ms
217,840 KB
testcase_38 AC 1,557 ms
215,852 KB
testcase_39 AC 1,680 ms
220,600 KB
testcase_40 AC 1,579 ms
218,728 KB
testcase_41 AC 1,691 ms
220,220 KB
testcase_42 AC 1,593 ms
219,484 KB
testcase_43 AC 1,638 ms
221,936 KB
testcase_44 AC 1,663 ms
221,360 KB
testcase_45 AC 1,635 ms
221,032 KB
testcase_46 AC 794 ms
174,664 KB
testcase_47 AC 1,597 ms
221,708 KB
testcase_48 AC 1,186 ms
211,524 KB
testcase_49 AC 1,567 ms
217,356 KB
testcase_50 AC 1,179 ms
214,316 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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