結果

問題 No.772 Dynamic Distance Sum
ユーザー gew1fw
提出日時 2025-06-12 20:38:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,930 bytes
コンパイル時間 363 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 86,528 KB
最終ジャッジ日時 2025-06-12 20:38:56
合計ジャッジ時間 10,343 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)

def main():
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N, Q = int(data[ptr]), int(data[ptr+1])
    ptr += 2
    queries = []
    S = 0
    sum_S = 0
    for _ in range(Q):
        t = int(data[ptr])
        if t == 1:
            a = int(data[ptr+1])
            b = int(data[ptr+2])
            c = int(data[ptr+3])
            queries.append((1, a, b, c))
            ptr +=4
        elif t == 2:
            a = int(data[ptr+1])
            b = int(data[ptr+2])
            queries.append((2, a, b))
            ptr +=3
        else:
            a = int(data[ptr+1])
            queries.append((3, a))
            ptr +=2

    X = [1]*(N+1)
    edges = defaultdict(set)
    edge_info = dict()

    for q in queries:
        if q[0] == 1:
            a = (q[1] -1 + S) % N +1
            b = (q[2] -1 + S) % N +1
            c = q[3]
            edges[a].add(b)
            edges[b].add(a)
            edge_info[(a, b)] = c
            edge_info[(b, a)] = c
        elif q[0] == 2:
            a = (q[1]-1 + S) % N +1
            b = (q[2]-1 + S) % N +1
            if a in edges and b in edges[a]:
                edges[a].remove(b)
                edges[b].remove(a)
                del edge_info[(a, b)]
                del edge_info[(b, a)]
        elif q[0] == 3:
            a = (q[1]-1 + S) % N +1
            X[a] = 1 - X[a]
            tree_nodes = set()
            visited = set()
            stack = [a]
            visited.add(a)
            tree_nodes.add(a)
            while stack:
                u = stack.pop()
                for v in edges[u]:
                    if v not in visited:
                        visited.add(v)
                        tree_nodes.add(v)
                        stack.append(v)
            total = 0
            min_sum = float('inf')
            for u in tree_nodes:
                s = 0
                for v in tree_nodes:
                    if u == v:
                        continue
                    path = []
                    visited_p = set()
                    stack_p = [(u, 0)]
                    found = False
                    while stack_p:
                        node, dist = stack_p.pop()
                        if node == v:
                            s += dist * X[v]
                            found = True
                            break
                        visited_p.add(node)
                        for neighbor in edges[node]:
                            if neighbor not in visited_p:
                                stack_p.append((neighbor, dist + edge_info[(node, neighbor)]))
                    if not found:
                        pass
                if s < min_sum:
                    min_sum = s
            S += min_sum
            sum_S += min_sum
            print(min_sum)

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