結果

問題 No.19 ステージの選択
ユーザー sjikisjiki
提出日時 2022-10-29 08:39:49
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,414 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 65,920 KB
最終ジャッジ日時 2024-07-06 09:09:20
合計ジャッジ時間 2,421 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
権限があれば一括ダウンロードができます

ソースコード

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,i)
    L.append(l)
ans = scc.scc()
for i in ans:
    ans1 = max(sum(L[::i]),ans1)
print(ans1)
0