結果
| 問題 | No.3814 Typical AWC Query |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-11-18 15:38:04 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 1,584 bytes |
| 記録 | |
| コンパイル時間 | 91 ms |
| コンパイル使用メモリ | 64,752 KB |
| 実行使用メモリ | 212,592 KB |
| 最終ジャッジ日時 | 2026-11-20 20:55:33 |
| 合計ジャッジ時間 | 12,439 ms |
|
ジャッジサーバーID (参考情報) |
judge5_0 / judge4_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 14 WA * 3 TLE * 1 -- * 2 |
ソースコード
# 【WA想定】A/W/C 以外の文字への変更を「W だった頂点の寄与を消すだけ」で済ませる。
# A/C の頂点がその他の文字になったとき、隣接 W の寄与と ca/cc の更新が漏れる。
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)
ca=[0]*n;cc=[0]*n
for v in range(n):
if s[v]=='A':
for u in adj[v]: ca[u]+=1
elif s[v]=='C':
for u in adj[v]: cc[u]+=1
ans=sum(ca[b]*cc[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 x not in 'AWC':
if o=='W': ans-=ca[v]*cc[v]
s[v]=x
elif o!=x:
if o=='W': ans-=ca[v]*cc[v]
elif o=='A':
for u in adj[v]:
if s[u]=='W': ans-=cc[u]
ca[u]-=1
elif o=='C':
for u in adj[v]:
if s[u]=='W': ans-=ca[u]
cc[u]-=1
s[v]=x
if x=='W': ans+=ca[v]*cc[v]
elif x=='A':
for u in adj[v]:
if s[u]=='W': ans+=cc[u]
ca[u]+=1
elif x=='C':
for u in adj[v]:
if s[u]=='W': ans+=ca[u]
cc[u]+=1
out.append(ans)
print(*out,sep='\n')
main()
sepa38