結果

問題 No.3814 Typical AWC Query
コンテスト
ユーザー sepa38
提出日時 2026-11-18 15:36:25
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 705 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

# 【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()
0