結果

問題 No.2311 [Cherry 5th Tune] Cherry Month
ユーザー 👑 KazunKazun
提出日時 2023-01-05 01:07:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,837 ms / 4,600 ms
コード長 2,936 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 228,996 KB
最終ジャッジ日時 2024-05-09 08:01:21
合計ジャッジ時間 66,285 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
53,120 KB
testcase_01 AC 41 ms
53,120 KB
testcase_02 AC 1,521 ms
191,384 KB
testcase_03 AC 581 ms
120,800 KB
testcase_04 AC 761 ms
112,848 KB
testcase_05 AC 675 ms
109,984 KB
testcase_06 AC 925 ms
120,116 KB
testcase_07 AC 660 ms
111,616 KB
testcase_08 AC 1,177 ms
174,436 KB
testcase_09 AC 996 ms
145,276 KB
testcase_10 AC 1,061 ms
149,504 KB
testcase_11 AC 1,067 ms
159,236 KB
testcase_12 AC 1,304 ms
167,692 KB
testcase_13 AC 1,149 ms
161,780 KB
testcase_14 AC 1,282 ms
169,220 KB
testcase_15 AC 1,246 ms
169,876 KB
testcase_16 AC 695 ms
110,196 KB
testcase_17 AC 1,423 ms
177,792 KB
testcase_18 AC 1,449 ms
169,700 KB
testcase_19 AC 1,237 ms
169,652 KB
testcase_20 AC 1,110 ms
161,708 KB
testcase_21 AC 1,163 ms
137,392 KB
testcase_22 AC 1,124 ms
139,096 KB
testcase_23 AC 979 ms
169,056 KB
testcase_24 AC 1,108 ms
165,428 KB
testcase_25 AC 1,001 ms
146,052 KB
testcase_26 AC 1,453 ms
181,644 KB
testcase_27 AC 1,060 ms
227,988 KB
testcase_28 AC 1,076 ms
228,516 KB
testcase_29 AC 1,051 ms
228,996 KB
testcase_30 AC 664 ms
141,728 KB
testcase_31 AC 673 ms
140,392 KB
testcase_32 AC 668 ms
140,928 KB
testcase_33 AC 1,113 ms
210,256 KB
testcase_34 AC 999 ms
209,168 KB
testcase_35 AC 1,097 ms
210,512 KB
testcase_36 AC 1,644 ms
214,444 KB
testcase_37 AC 1,674 ms
218,316 KB
testcase_38 AC 1,677 ms
216,388 KB
testcase_39 AC 1,816 ms
220,876 KB
testcase_40 AC 1,769 ms
217,256 KB
testcase_41 AC 1,837 ms
220,224 KB
testcase_42 AC 1,727 ms
216,940 KB
testcase_43 AC 1,812 ms
219,896 KB
testcase_44 AC 1,821 ms
220,924 KB
testcase_45 AC 1,745 ms
219,188 KB
testcase_46 AC 826 ms
173,656 KB
testcase_47 AC 1,789 ms
219,972 KB
testcase_48 AC 1,363 ms
212,728 KB
testcase_49 AC 1,750 ms
213,212 KB
testcase_50 AC 1,256 ms
208,996 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