結果

問題 No.19 ステージの選択
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0