結果

問題 No.2311 [Cherry 5th Tune] Cherry Month
ユーザー KazunKazun
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
52,736 KB
testcase_01 AC 39 ms
53,376 KB
testcase_02 AC 1,489 ms
191,416 KB
testcase_03 AC 508 ms
120,420 KB
testcase_04 AC 671 ms
112,584 KB
testcase_05 AC 604 ms
109,600 KB
testcase_06 AC 848 ms
119,608 KB
testcase_07 AC 562 ms
111,616 KB
testcase_08 AC 1,107 ms
174,508 KB
testcase_09 AC 918 ms
145,420 KB
testcase_10 AC 989 ms
149,240 KB
testcase_11 AC 1,004 ms
158,844 KB
testcase_12 AC 1,201 ms
167,564 KB
testcase_13 AC 1,056 ms
161,220 KB
testcase_14 AC 1,206 ms
169,272 KB
testcase_15 AC 1,172 ms
169,736 KB
testcase_16 AC 670 ms
109,556 KB
testcase_17 AC 1,374 ms
177,144 KB
testcase_18 AC 1,367 ms
169,564 KB
testcase_19 AC 1,162 ms
169,572 KB
testcase_20 AC 1,021 ms
162,024 KB
testcase_21 AC 1,096 ms
136,884 KB
testcase_22 AC 1,011 ms
139,108 KB
testcase_23 AC 919 ms
169,056 KB
testcase_24 AC 1,029 ms
165,052 KB
testcase_25 AC 937 ms
146,244 KB
testcase_26 AC 1,339 ms
181,576 KB
testcase_27 AC 1,001 ms
227,740 KB
testcase_28 AC 1,019 ms
228,504 KB
testcase_29 AC 1,001 ms
228,956 KB
testcase_30 AC 647 ms
141,352 KB
testcase_31 AC 642 ms
140,424 KB
testcase_32 AC 641 ms
140,752 KB
testcase_33 AC 1,058 ms
210,196 KB
testcase_34 AC 956 ms
208,396 KB
testcase_35 AC 1,043 ms
210,504 KB
testcase_36 AC 1,557 ms
214,572 KB
testcase_37 AC 1,556 ms
218,120 KB
testcase_38 AC 1,562 ms
216,204 KB
testcase_39 AC 1,718 ms
220,432 KB
testcase_40 AC 1,659 ms
216,752 KB
testcase_41 AC 1,731 ms
219,840 KB
testcase_42 AC 1,648 ms
216,332 KB
testcase_43 AC 1,697 ms
219,536 KB
testcase_44 AC 1,948 ms
220,540 KB
testcase_45 AC 1,658 ms
219,348 KB
testcase_46 AC 798 ms
173,396 KB
testcase_47 AC 1,691 ms
219,556 KB
testcase_48 AC 1,275 ms
212,768 KB
testcase_49 AC 1,602 ms
212,968 KB
testcase_50 AC 1,200 ms
208,744 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