結果

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

ソースコード

diff # 

import sys, math

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。各頂点 v の隣接集合
    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判定の閾値 TH: 初期辺数からおおよそ sqrt(2*M) 程度
    TH = int(math.sqrt(2*M)) + 1
    
    # heavy[v] True なら頂点 v は heavy とする
    heavy = [False]*(N+1)
    # heavy_sum[v]: 頂点 v が heavy なら、その隣接頂点の重み和を保持
    heavy_sum = [0]*(N+1)
    # heavy_nbr[v]: 頂点 v の隣接頂点のうち heavy なものの集合
    heavy_nbr = [set() for _ in range(N+1)]
    
    # 初期 heavy 判定（動的に heavy への昇格は一度だけ）
    for v in range(1, N+1):
        if len(adj[v]) >= TH:
            heavy[v] = True
    # heavy 頂点について heavy_sum と heavy_nbr を初期化
    for v in range(1, N+1):
        if heavy[v]:
            heavy_sum[v] = sum(A[w] for w in adj[v])
            for w in adj[v]:
                heavy_nbr[w].add(v)
    
    out_lines = []
    for _ in range(Q):
        t = int(next(it))
        if t == 1:
            # クエリ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_sum[w] = s
                        for nb in adj[w]:
                            heavy_nbr[nb].add(w)
        elif t == 2:
            # クエリ2: 頂点 p の重みを a に更新
            p = int(next(it))
            a = int(next(it))
            diff = a - A[p]
            A[p] = a
            # p を隣接する heavy 頂点について、heavy_sum を更新
            for h in heavy_nbr[p]:
                heavy_sum[h] += diff
        else:
            # クエリ3: 頂点 c の隣接頂点の重み和を出力
            c = int(next(it))
            if heavy[c]:
                out_lines.append(str(heavy_sum[c]))
            else:
                s = 0
                for w in adj[c]:
                    s += A[w]
                out_lines.append(str(s))
    
    sys.stdout.write("\n".join(out_lines) + "\n")

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