結果
| 問題 | No.3814 Typical AWC Query |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-11-18 15:37:03 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 2,716 bytes |
| 記録 | |
| コンパイル時間 | 99 ms |
| コンパイル使用メモリ | 64,252 KB |
| 実行使用メモリ | 262,596 KB |
| 最終ジャッジ日時 | 2026-11-20 20:55:19 |
| 合計ジャッジ時間 | 11,871 ms |
|
ジャッジサーバーID (参考情報) |
judge3_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 17 WA * 3 |
ソースコード
# 【WA想定】平方分割もどき。次数 > B=floor(sqrt(2M)) の頂点を heavy とし、
# - heavy は隣接頂点に ca/cc を push しない(A(x) = 軽い隣接からの ca_l[x] + heavy 隣接を数える)
# - heavy h には SWA[h] = Σ_{b∈N(h), S_b=W} A(b), SWC[h] = Σ C(b) を持たせる
# SWA/SWC を「隣接 b が W になる/やめる」ときしか更新せず、
# b の A(b)/C(b) が変わったとき(2ホップ先の変化)の更新を忘れている。
# サンプルは heavy 頂点が存在しないので通ってしまう。
import sys
def main():
d=sys.stdin.buffer.read().split();n,m=int(d[0]),int(d[1]);s=list(d[2].decode());p=3
adj=[[] for _ in range(n)]
for _ in range(m):
u,v=int(d[p])-1,int(d[p+1])-1;p+=2;adj[u].append(v);adj[v].append(u)
B=int((2*m)**0.5)
heavy=[len(adj[v])>B for v in range(n)]
hadj=[[u for u in adj[v] if heavy[u]] for v in range(n)]
ca=[0]*n;cc=[0]*n
for v in range(n):
if heavy[v]: continue
if s[v]=='A':
for u in adj[v]: ca[u]+=1
elif s[v]=='C':
for u in adj[v]: cc[u]+=1
def A(x): return ca[x]+sum(1 for h in hadj[x] if s[h]=='A')
def C(x): return cc[x]+sum(1 for h in hadj[x] if s[h]=='C')
SWA=[0]*n;SWC=[0]*n
for h in range(n):
if heavy[h]:
for b in adj[h]:
if s[b]=='W': SWA[h]+=A(b);SWC[h]+=C(b)
ans=sum(A(b)*C(b) for b in range(n) if s[b]=='W')
q=int(d[p]);p+=1;out=[]
for _ in range(q):
v=int(d[p])-1;x=d[p+1].decode();p+=2;o=s[v]
if o!=x:
if o=='W':
a,c=A(v),C(v);ans-=a*c
for h in hadj[v]: SWA[h]-=a;SWC[h]-=c
elif o=='A':
if heavy[v]: ans-=SWC[v]
else:
for b in adj[v]:
if s[b]=='W': ans-=C(b)
ca[b]-=1
elif o=='C':
if heavy[v]: ans-=SWA[v]
else:
for b in adj[v]:
if s[b]=='W': ans-=A(b)
cc[b]-=1
s[v]=x
if x=='W':
a,c=A(v),C(v);ans+=a*c
for h in hadj[v]: SWA[h]+=a;SWC[h]+=c
elif x=='A':
if heavy[v]: ans+=SWC[v]
else:
for b in adj[v]:
if s[b]=='W': ans+=C(b)
ca[b]+=1
elif x=='C':
if heavy[v]: ans+=SWA[v]
else:
for b in adj[v]:
if s[b]=='W': ans+=A(b)
cc[b]+=1
out.append(ans)
print(*out,sep='\n')
main()
sepa38