結果
問題 |
No.922 東北きりきざむたん
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:26:05 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,904 bytes |
コンパイル時間 | 157 ms |
コンパイル使用メモリ | 82,080 KB |
実行使用メモリ | 262,464 KB |
最終ジャッジ日時 | 2025-06-12 15:26:26 |
合計ジャッジ時間 | 7,762 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 3 WA * 2 TLE * 2 -- * 19 |
ソースコード
import sys from collections import deque 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) component = [0] * (N + 1) current_component = 0 component_info = [] for u in range(1, N + 1): if not visited[u]: current_component += 1 q = deque() q.append(u) visited[u] = True comp_nodes = [] while q: node = q.popleft() comp_nodes.append(node) for v in edges[node]: if not visited[v]: visited[v] = True q.append(v) for node in comp_nodes: component[node] = current_component component_info.append(comp_nodes) in_time = [0] * (N + 1) out_time = [0] * (N + 1) depth = [0] * (N + 1) parent = [0] * (N + 1) time_counter = 0 for comp in component_info: root = comp[0] stack = [(root, False)] parent[root] = 0 while stack: node, processed = stack.pop() if processed: out_time[node] = time_counter time_counter += 1 else: in_time[node] = time_counter time_counter += 1 stack.append((node, True)) children = [] for v in edges[node]: if component[v] == component[node] and v != parent[node]: children.append(v) children.sort(reverse=True) for v in children: if parent[v] == 0: parent[v] = node depth[v] = depth[node] + 1 stack.append((v, False)) def lca(u, v): if depth[u] < depth[v]: u, v = v, u while depth[u] > depth[v]: u = parent[u] if u == v: return u while parent[u] != parent[v]: u = parent[u] v = parent[v] return parent[u] distance_same = 0 S = dict() for _ in range(Q): a, b = map(int, sys.stdin.readline().split()) if component[a] == component[b]: ancestor = lca(a, b) dist = depth[a] + depth[b] - 2 * depth[ancestor] distance_same += dist else: if component[a] not in S: S[component[a]] = [] S[component[a]].append(a) if component[b] not in S: S[component[b]] = [] S[component[b]].append(b) total = distance_same for comp in component_info: comp_id = component[comp[0]] if comp_id not in S: continue S_C = S[comp_id] if not S_C: continue root = comp[0] current_u = root sum_dist = [0] * (N + 1) for s in S_C: sum_dist[s] += 1 stack = [current_u] best_sum = float('inf') best_u = current_u for u in S_C: temp_sum = 0 for v in S_C: ancestor = lca(u, v) temp_sum += depth[u] + depth[v] - 2 * depth[ancestor] if temp_sum < best_sum: best_sum = temp_sum best_u = u current_u = best_u current_sum = 0 for s in S_C: ancestor = lca(current_u, s) current_sum += depth[current_u] + depth[s] - 2 * depth[ancestor] total += current_sum print(total) if __name__ == "__main__": main()