結果

問題 No.3025 Chocol∀te
コンテスト
ユーザー detteiuu
提出日時 2025-02-16 17:40:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,695 ms / 2,000 ms
コード長 1,850 bytes
コンパイル時間 414 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 137,312 KB
最終ジャッジ日時 2025-02-16 17:41:30
合計ジャッジ時間 44,933 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 77
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, M = map(int, input().split())
G = [set() for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u-1].add(v-1)
    G[v-1].add(u-1)
A = list(map(int, input().split()))
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]

route = int((10**5)**0.5)
big = set()
D = dict()
for i in range(N):
    if route <= len(G[i]):
        big.add(i)
        SUM = 0
        for j in G[i]:
            SUM += A[j]
        D[i] = SUM

for i in range(Q):
    if query[i][0] == 1:
        u, v = query[i][1:]
        u, v = u-1, v-1
        if v in G[u]:
            G[u].remove(v)
            G[v].remove(u)
            if route <= len(G[u]):
                D[u] -= A[v]
            if route <= len(G[v]):
                D[v] -= A[u]
            if len(G[u])+1 == route:
                big.remove(u)
            if len(G[v])+1 == route:
                big.remove(v)
        else:
            G[u].add(v)
            G[v].add(u)
            if route+1 <= len(G[u]):
                D[u] += A[v]
            if route+1 <= len(G[v]):
                D[v] += A[u]
            if len(G[u]) == route:
                big.add(u)
                SUM = 0
                for j in G[u]:
                    SUM += A[j]
                D[u] = SUM
            if len(G[v]) == route:
                big.add(v)
                SUM = 0
                for j in G[v]:
                    SUM += A[j]
                D[v] = SUM
    elif query[i][0] == 2:
        p, a = query[i][1:]
        p -= 1
        pre = A[p]
        for b in big:
            if p in G[b]:
                D[b] -= pre
                D[b] += a
        A[p] = a
    else:
        c = query[i][1]-1
        if c in big:
            print(D[c])
        else:
            ans = 0
            for j in G[c]:
                ans += A[j]
            print(ans)
0