結果
問題 |
No.19 ステージの選択
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:58:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 44 ms / 5,000 ms |
コード長 | 4,404 bytes |
コンパイル時間 | 222 ms |
コンパイル使用メモリ | 82,188 KB |
実行使用メモリ | 56,692 KB |
最終ジャッジ日時 | 2025-03-31 17:59:36 |
合計ジャッジ時間 | 2,148 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
import sys from sys import stdin from collections import defaultdict, deque sys.setrecursionlimit(1000000) def main(): N = int(stdin.readline()) L = [0] * (N + 1) S = [0] * (N + 1) for i in range(1, N + 1): line = stdin.readline().split() L[i] = int(line[0]) S[i] = int(line[1]) # Build graph adj = [[] for _ in range(N + 1)] for i in range(1, N + 1): adj[i].append(S[i]) # Kosaraju's algorithm to find SCC visited = [False] * (N + 1) order = [] def dfs(u): stack = [(u, False)] while stack: node, processed = stack.pop() if processed: order.append(node) continue if visited[node]: continue visited[node] = True stack.append((node, True)) for v in adj[node]: if not visited[v]: stack.append((v, False)) for u in range(1, N + 1): if not visited[u]: dfs(u) transpose_adj = [[] for _ in range(N + 1)] for u in range(1, N + 1): for v in adj[u]: transpose_adj[v].append(u) visited = [False] * (N + 1) scc = [] while order: u = order.pop() if not visited[u]: stack = [u] visited[u] = True component = [] while stack: node = stack.pop() component.append(node) for v in transpose_adj[node]: if not visited[v]: visited[v] = True stack.append(v) scc.append(component) # Build DAG between SCCs and get topo order (in reverse) # Assign component index comp_id = [0] * (N + 1) for i, component in enumerate(scc): for node in component: comp_id[node] = i dag_adj = defaultdict(set) for u in range(1, N + 1): for v in adj[u]: if comp_id[u] != comp_id[v]: dag_adj[comp_id[u]].add(comp_id[v]) # Topological sort (Kahn's algorithm) in_degree = defaultdict(int) for u in dag_adj: for v in dag_adj[u]: in_degree[v] += 1 queue = deque() for i in range(len(scc)): if in_degree.get(i, 0) == 0: queue.append(i) topo_order = [] while queue: u = queue.popleft() topo_order.append(u) for v in dag_adj[u]: in_degree[v] -= 1 if in_degree[v] == 0: queue.append(v) # Process SCC in reverse topological order topo_order = topo_order[::-1] processed = [False] * (N + 1) total = 0.0 order_of_processing = [] for comp_idx in topo_order: component = scc[comp_idx] if not component: continue # Find the node with minimum Li/2 min_val = float('inf') head = None for node in component: val = L[node] / 2 if val < min_val: min_val = val head = node # head must be processed first order_in_comp = [] temp_processed = [False] * (N + 1) temp_processed[head] = True order_in_comp.append(head) remaining = set(component) remaining.remove(head) while remaining: candidates = [] for node in remaining: s_node = S[node] if (processed[s_node] or temp_processed[s_node]) and (s_node not in remaining or temp_processed[s_node]): candidates.append((-L[node]/2, node)) # max heap by using negative if not candidates: # pick any node (must be part of the cycle) node = next(iter(remaining)) order_in_comp.append(node) temp_processed[node] = True remaining.remove(node) else: candidates.sort() _, best = candidates[0] order_in_comp.append(best) temp_processed[best] = True remaining.remove(best) for node in order_in_comp: if processed[S[node]]: total += L[node] / 2 else: total += L[node] processed[node] = True print("{0:.1f}".format(total)) if __name__ == '__main__': main()