結果

問題 No.3025 Chocol∀te
ユーザー Vincent Shaw
提出日時 2025-02-14 21:44:14
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 3,360 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 206,472 KB
最終ジャッジ日時 2025-02-14 21:45:14
合計ジャッジ時間 54,509 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 74 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys, math
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    
    # 1-indexed：各頂点の隣接頂点集合
    adj = [set() for _ in range(N+1)]
    for _ in range(M):
        u = int(next(it))
        v = int(next(it))
        adj[u].add(v)
        adj[v].add(u)
    
    # 各頂点の重み A[1..N]
    A = [0]*(N+1)
    for i in range(1, N+1):
        A[i] = int(next(it))
    
    Q = int(next(it))
    
    # heavy判定の閾値: 初期辺数から sqrt(2*M) 程度
    TH = int(math.sqrt(2*M)) + 1
    
    heavy = [False]*(N+1)      # heavy[v] Trueなら heavy とする
    heavy_sum = [0]*(N+1)      # heavyな頂点 v の隣接頂点の重み和
    heavy_nbr = [set() for _ in range(N+1)]  # 各頂点 v について、隣接する heavy 頂点
    
    # 初期 heavy 判定
    for v in range(1, N+1):
        if len(adj[v]) >= TH:
            heavy[v] = True
    # heavy_sum, heavy_nbr の初期化
    for v in range(1, N+1):
        if heavy[v]:
            s = 0
            for w in adj[v]:
                s += A[w]
            heavy_sum[v] = s
            for w in adj[v]:
                heavy_nbr[w].add(v)
    
    out_lines = []
    
    for _ in range(Q):
        t = int(next(it))
        if t == 1:
            u = int(next(it))
            v = int(next(it))
            if v in adj[u]:
                # 辺 (u,v) が存在 -> 削除
                adj[u].remove(v)
                adj[v].remove(u)
                if heavy[u]:
                    heavy_sum[u] -= A[v]
                if heavy[v]:
                    heavy_sum[v] -= A[u]
                if heavy[v]:
                    heavy_nbr[u].discard(v)
                if heavy[u]:
                    heavy_nbr[v].discard(u)
            else:
                # 辺追加
                adj[u].add(v)
                adj[v].add(u)
                if heavy[u]:
                    heavy_sum[u] += A[v]
                if heavy[v]:
                    heavy_sum[v] += A[u]
                if heavy[v]:
                    heavy_nbr[u].add(v)
                if heavy[u]:
                    heavy_nbr[v].add(u)
                # 追加後、もし u または v が light で、かつ次数が閾値に達したなら heavy に昇格
                for w in (u, v):
                    if not heavy[w] and len(adj[w]) >= TH:
                        heavy[w] = True
                        s = 0
                        for nb in adj[w]:
                            s += A[nb]
                            heavy_nbr[nb].add(w)
                        heavy_sum[w] = s
        elif t == 2:
            p = int(next(it))
            a = int(next(it))
            d = a - A[p]
            A[p] = a
            # p の重み更新：p を隣接する heavy 頂点の heavy_sum を更新
            for h in heavy_nbr[p]:
                heavy_sum[h] += d
        else:  # t == 3
            c = int(next(it))
            if heavy[c]:
                res = heavy_sum[c]
            else:
                s = 0
                for w in adj[c]:
                    s += A[w]
                res = s
            out_lines.append(str(res))
    
    sys.stdout.write("\n".join(out_lines) + "\n")

if __name__ == '__main__':
    main()
0