結果

問題 No.19 ステージの選択
ユーザー sjikisjiki
提出日時 2022-10-29 09:06:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,511 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 81,944 KB
実行使用メモリ 55,132 KB
最終ジャッジ日時 2024-07-06 09:30:02
合計ジャッジ時間 1,780 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
52,768 KB
testcase_01 AC 37 ms
52,072 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 34 ms
52,216 KB
testcase_12 AC 33 ms
53,280 KB
testcase_13 AC 37 ms
52,832 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SCC:

    def __init__(self, n):
        self.n = n
        self.graph = [[] for i in range(n)]
        self.graph_rev = [[] for i in range(n)]
        self.used = [False]*n

    def add_edge(self, fr, to):
        if fr == to:
            return
        self.graph[fr].append(to)
        self.graph_rev[to].append(fr)

    def dfs(self, node, graph):
        self.used[node] = True
        for nex in graph[node]:
            if self.used[nex]:
                continue
            self.dfs(nex,graph)
        self.order.append(node)

    def first_dfs(self):
        self.used = [False]*self.n
        self.order = []
        for i in range(self.n):
            if self.used[i]:
                continue
            self.dfs(i,self.graph)
    
    def second_dfs(self):
        self.used = [False]*self.n
        self.ans = []
        for node in reversed(self.order):
            if self.used[node]:
                continue
            self.used[node] = True
            self.order = []
            self.dfs(node, self.graph_rev)
            #self.order.reverse()
            self.ans.append(self.order)

    def scc(self):
        self.first_dfs()
        self.second_dfs()
        return self.ans


N = int(input())
scc = SCC(N)
L = []
for i in range(N):
    l,S = map(int,input().split())
    scc.add_edge(S-1,i)
    L.append(l)
ans = scc.scc()
ans1 = 0
for i in ans:
    tmp = 0
    m= 10 ** 5
    for j in i:
        tmp += L[j]
        m = min(L[j],m)
    ans1 = max((tmp+m)/2,ans1)
print(ans1)
0