結果

問題 No.19 ステージの選択
ユーザー toyuzukotoyuzuko
提出日時 2020-05-30 14:02:48
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 35 ms / 5,000 ms
コード長 2,435 bytes
コンパイル時間 89 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-04-25 05:50:05
合計ジャッジ時間 1,896 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
10,880 KB
testcase_01 AC 31 ms
10,880 KB
testcase_02 AC 33 ms
10,880 KB
testcase_03 AC 33 ms
10,880 KB
testcase_04 AC 35 ms
11,008 KB
testcase_05 AC 34 ms
11,008 KB
testcase_06 AC 32 ms
10,880 KB
testcase_07 AC 33 ms
10,752 KB
testcase_08 AC 32 ms
11,008 KB
testcase_09 AC 33 ms
10,752 KB
testcase_10 AC 31 ms
10,880 KB
testcase_11 AC 32 ms
10,880 KB
testcase_12 AC 30 ms
10,880 KB
testcase_13 AC 32 ms
10,752 KB
testcase_14 AC 31 ms
10,752 KB
testcase_15 AC 33 ms
10,752 KB
testcase_16 AC 32 ms
10,880 KB
testcase_17 AC 32 ms
10,752 KB
testcase_18 AC 32 ms
10,752 KB
testcase_19 AC 32 ms
10,880 KB
testcase_20 AC 30 ms
10,880 KB
testcase_21 AC 32 ms
10,752 KB
testcase_22 AC 32 ms
10,880 KB
testcase_23 AC 32 ms
10,752 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Graph(): #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.rev = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append(e[1] - indexed)
            self.rev[e[1] - indexed].append(e[0] - indexed)
            self.deg[e[1] - indexed] += 1

    def strongry_connected(self):
        group = [None for _ in range(self.n)]
        used = [0 for _ in range(self.n)]
        order = []
        for s in range(self.n):
            if not used[s]:
                stack = [s]
                used[s] = 1
                while stack:
                    node = stack.pop()
                    movable = False
                    for adj in self.graph[node]:
                        if not used[adj]:
                            movable = True
                            used[adj] = 1
                            stack.append(node)
                            stack.append(adj)
                            break
                    if not movable:
                        order.append(node)
        used = [0 for _ in range(self.n)]
        count = 0
        for s in order[::-1]:
            if not used[s]:
                stack = [s]
                group[s] = count
                while stack:
                    node = stack.pop()
                    used[node] = 1
                    for adj in self.rev[node]:
                        if not used[adj]:
                            group[adj] = count
                            stack.append(adj)
                count += 1
        return group, count

import sys
input = sys.stdin.readline

N = int(input())
L = []
E = []

for i in range(N):
    l, s = map(int, input().split())
    L.append(l)
    E.append((s, i + 1))

g = Graph(N, E)
group, count = g.strongry_connected()

group_to_node = [[] for _ in range(count)]

for i in range(N):
    group_to_node[group[i]].append(i)

new_edge = set()

for a, b in E:
    if group[a - 1] == group[b - 1]:
        continue
    new_edge.add((group[a - 1], group[b - 1]))

compressed_graph = Graph(count, new_edge, 0)
res = 0

for i in range(count):
    difficulty = []
    for j in group_to_node[i]:
        difficulty.append(L[j])
    if compressed_graph.deg[i] == 0:
        res += (sum(difficulty) + min(difficulty)) / 2
    else:
        res += sum(difficulty) / 2

print(res)
0