結果
| 問題 | No.3814 Typical AWC Query |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-11-18 15:36:25 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 705 bytes |
| 記録 | |
| コンパイル時間 | 83 ms |
| コンパイル使用メモリ | 63,884 KB |
| 実行使用メモリ | 151,140 KB |
| 最終ジャッジ日時 | 2026-11-20 20:55:06 |
| 合計ジャッジ時間 | 7,351 ms |
|
ジャッジサーバーID (参考情報) |
judge4_0 / judge1_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 5 TLE * 1 -- * 14 |
ソースコード
# 【TLE想定】クエリごとに全体を再計算 O(Q(N+M)) = 2e4 * 1e6
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
U=[0]*m;V=[0]*m
for i in range(m):
U[i],V[i]=int(d[p])-1,int(d[p+1])-1;p+=2
q=int(d[p]);p+=1;out=[]
for _ in range(q):
v=int(d[p])-1;x=d[p+1].decode();p+=2;s[v]=x
ca=[0]*n;cc=[0]*n
for i in range(m):
a,b=U[i],V[i]
if s[a]=='A': ca[b]+=1
elif s[a]=='C': cc[b]+=1
if s[b]=='A': ca[a]+=1
elif s[b]=='C': cc[a]+=1
out.append(sum(ca[i]*cc[i] for i in range(n) if s[i]=='W'))
print(*out,sep='\n')
main()
sepa38