結果

問題 No.19 ステージの選択
ユーザー Ryota_Bannai
提出日時 2022-08-01 22:36:35
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 32 ms / 5,000 ms
コード長 1,725 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-07-22 13:28:47
合計ジャッジ時間 1,852 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**9)
readline = sys.stdin.readline


def dfs(x, G, visited, log):
   visited[x] = True
   for y in G[x]:
       if visited[y]:
           continue
       dfs(y, G, visited, log)
   log.append(x)


def main():
   N = int(readline())
   fr = [[] for _ in range(N)]
   to = [[] for _ in range(N)]
   difficulty = [0]*N
   for x in range(N):
       d, y = map(int, readline().split())
       y -= 1
       fr[x].append(y)
       to[y].append(x)
       difficulty[x] = d

   visited = [False]*N
   log = []
   for x in range(N):
       if visited[x]:
           continue
       dfs(x, to, visited, log)
   log.reverse()

   visited = [False]*N
   groups = []
   for x in log:
       if visited[x]:
           continue
       group = []
       dfs(x, fr, visited, group)
       groups.append(group)
   I = len(groups)
   V_to_I = [-1]*N

   diff_of_I = [-1]*I
   for i, group in enumerate(groups):
       min_diff = 1000
       sum_diff = 0
       for x in group:
           V_to_I[x] = i
           min_diff = min(min_diff, difficulty[x])
           sum_diff += difficulty[x]
       diff_of_I[i] = (min_diff + sum_diff) / 2

   DAG = [[] for _ in range(I)]
   for x in range(N):
       i = V_to_I[x]
       for y in to[x]:
           j = V_to_I[y]
           if i != j:
               DAG[i].append(j)

   ans = 0
   visited = [False]*I
   for i in range(I):
       if visited[i]:
           continue
       component = []
       dfs(i, DAG, visited, component)
       component.reverse()
       for i, c in enumerate(component):
           if i == 0:
               ans += diff_of_I[c]
           else:
               ans += diff_of_I[c] / 2
   print(ans)


if __name__ == "__main__":
   main()
0