結果
| 問題 | No.3814 Typical AWC Query |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-11-18 15:36:00 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 1,498 bytes |
| 記録 | |
| コンパイル時間 | 91 ms |
| コンパイル使用メモリ | 64,292 KB |
| 実行使用メモリ | 212,640 KB |
| 最終ジャッジ日時 | 2026-11-20 20:55:05 |
| 合計ジャッジ時間 | 13,389 ms |
|
ジャッジサーバーID (参考情報) |
judge3_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 17 TLE * 1 -- * 2 |
ソースコード
# 【TLE想定】各頂点の A隣接数 ca[], C隣接数 cc[] を持ち、クエリごとに v の隣接を全部なめる
# 正しいが O(Σ deg(v_i))。スター中心へのクエリを繰り返すと 2e4 * 5e5 = 1e10 で TLE
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