結果
| 問題 | No.3814 Typical AWC Query |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-11-18 15:38:29 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 1,476 bytes |
| 記録 | |
| コンパイル時間 | 96 ms |
| コンパイル使用メモリ | 64,300 KB |
| 実行使用メモリ | 212,872 KB |
| 最終ジャッジ日時 | 2026-11-20 20:55:36 |
| 合計ジャッジ時間 | 13,339 ms |
|
ジャッジサーバーID (参考情報) |
judge1_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 11 WA * 6 TLE * 1 -- * 2 |
ソースコード
# 【WA想定】「中心 b は W なので W の頂点の ca/cc だけ管理すればよい」と考え、
# 隣接頂点の ca/cc を更新するとき W の隣接頂点にしか反映しない。
# 非 W の頂点が後で 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 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