結果

問題 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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

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())))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0