結果

問題 No.19 ステージの選択
ユーザー sjiki
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 24
権限があれば一括ダウンロードができます

ソースコード

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