結果
問題 |
No.922 東北きりきざむたん
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:39:55 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,317 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 82,140 KB |
実行使用メモリ | 176,352 KB |
最終ジャッジ日時 | 2025-06-12 20:40:17 |
合計ジャッジ時間 | 16,440 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 WA * 19 |
ソースコード
import sys from collections import deque, defaultdict def main(): sys.setrecursionlimit(1 << 25) N, M, Q = map(int, sys.stdin.readline().split()) edges = [[] for _ in range(N+1)] for _ in range(M): u, v = map(int, sys.stdin.readline().split()) edges[u].append(v) edges[v].append(u) visited = [False] * (N + 1) components = [] component_id = [0] * (N + 1) parent = [0] * (N + 1) up = [[-1] * 20 for _ in range(N + 1)] depth = [0] * (N + 1) for u in range(1, N + 1): if not visited[u]: q = deque() q.append(u) visited[u] = True component = [] component.append(u) parent[u] = -1 while q: v = q.popleft() for neighbor in edges[v]: if not visited[neighbor]: visited[neighbor] = True q.append(neighbor) parent[neighbor] = v component.append(neighbor) components.append(component) for node in component: component_id[node] = len(components) - 1 root = component[0] depth[root] = 0 for node in component: up[node][0] = parent[node] if parent[node] != -1 else -1 for k in range(1, 20): for node in component: if up[node][k-1] != -1: up[node][k] = up[up[node][k-1]][k-1] else: up[node][k] = -1 q = deque() q.append(root) depth[root] = 0 while q: v = q.popleft() for neighbor in edges[v]: if parent[neighbor] == v and neighbor != parent[v]: depth[neighbor] = depth[v] + 1 q.append(neighbor) sum_same = 0 P = defaultdict(list) for _ in range(Q): a, b = map(int, sys.stdin.readline().split()) if component_id[a] == component_id[b]: c = component_id[a] u, v = a, b if depth[u] < depth[v]: u, v = v, u for k in range(19, -1, -1): if depth[u] - (1 << k) >= depth[v]: u = up[u][k] if u == v: lca_node = u else: for k in range(19, -1, -1): if up[u][k] != -1 and up[u][k] != up[v][k]: u = up[u][k] v = up[v][k] lca_node = parent[u] distance = depth[a] + depth[b] - 2 * depth[lca_node] sum_same += distance else: P[component_id[a]].append(a) P[component_id[b]].append(b) sum_diff = 0 for c in range(len(components)): component = components[c] if c not in P: continue P_C = P[c] if not P_C: continue children = defaultdict(list) for node in component: if parent[node] != -1: children[parent[node]].append(node) root = component[0] weight = defaultdict(int) for u in P_C: weight[u] = 1 cnt = defaultdict(int) res = defaultdict(int) stack = [(root, False)] while stack: u, done = stack.pop() if done: cnt[u] = 0 res[u] = 0 for v in children[u]: cnt[u] += cnt[v] res[u] += res[v] + cnt[v] if weight[u]: cnt[u] += 1 else: stack.append((u, True)) for v in children[u]: stack.append((v, False)) total = len(P_C) stack = [root] while stack: u = stack.pop() for v in children[u]: res[v] = res[u] - cnt[v] + (total - cnt[v]) stack.append(v) min_res = min(res.values()) sum_diff += min_res print(sum_same + sum_diff) if __name__ == "__main__": main()