結果

問題 No.3814 Typical AWC Query
コンテスト
ユーザー sepa38
提出日時 2026-11-18 15:37:03
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,716 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 99 ms
コンパイル使用メモリ 64,252 KB
実行使用メモリ 262,596 KB
最終ジャッジ日時 2026-11-20 20:55:19
合計ジャッジ時間 11,871 ms
ジャッジサーバーID
(参考情報)
judge3_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

# 【WA想定】平方分割もどき。次数 > B=floor(sqrt(2M)) の頂点を heavy とし、
#  - heavy は隣接頂点に ca/cc を push しない(A(x) = 軽い隣接からの ca_l[x] + heavy 隣接を数える)
#  - heavy h には SWA[h] = Σ_{b∈N(h), S_b=W} A(b), SWC[h] = Σ C(b) を持たせる
# SWA/SWC を「隣接 b が W になる/やめる」ときしか更新せず、
# b の A(b)/C(b) が変わったとき(2ホップ先の変化)の更新を忘れている。
# サンプルは heavy 頂点が存在しないので通ってしまう。
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)
    B=int((2*m)**0.5)
    heavy=[len(adj[v])>B for v in range(n)]
    hadj=[[u for u in adj[v] if heavy[u]] for v in range(n)]
    ca=[0]*n;cc=[0]*n
    for v in range(n):
        if heavy[v]: continue
        if s[v]=='A':
            for u in adj[v]: ca[u]+=1
        elif s[v]=='C':
            for u in adj[v]: cc[u]+=1
    def A(x): return ca[x]+sum(1 for h in hadj[x] if s[h]=='A')
    def C(x): return cc[x]+sum(1 for h in hadj[x] if s[h]=='C')
    SWA=[0]*n;SWC=[0]*n
    for h in range(n):
        if heavy[h]:
            for b in adj[h]:
                if s[b]=='W': SWA[h]+=A(b);SWC[h]+=C(b)
    ans=sum(A(b)*C(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':
                a,c=A(v),C(v);ans-=a*c
                for h in hadj[v]: SWA[h]-=a;SWC[h]-=c
            elif o=='A':
                if heavy[v]: ans-=SWC[v]
                else:
                    for b in adj[v]:
                        if s[b]=='W': ans-=C(b)
                        ca[b]-=1
            elif o=='C':
                if heavy[v]: ans-=SWA[v]
                else:
                    for b in adj[v]:
                        if s[b]=='W': ans-=A(b)
                        cc[b]-=1
            s[v]=x
            if x=='W':
                a,c=A(v),C(v);ans+=a*c
                for h in hadj[v]: SWA[h]+=a;SWC[h]+=c
            elif x=='A':
                if heavy[v]: ans+=SWC[v]
                else:
                    for b in adj[v]:
                        if s[b]=='W': ans+=C(b)
                        ca[b]+=1
            elif x=='C':
                if heavy[v]: ans+=SWA[v]
                else:
                    for b in adj[v]:
                        if s[b]=='W': ans+=A(b)
                        cc[b]+=1
        out.append(ans)
    print(*out,sep='\n')
main()
0