結果
問題 |
No.19 ステージの選択
|
ユーザー |
![]() |
提出日時 | 2023-06-11 23:43:30 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,303 ms / 5,000 ms |
コード長 | 743 bytes |
コンパイル時間 | 407 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 59,920 KB |
最終ジャッジ日時 | 2025-01-03 05:28:15 |
合計ジャッジ時間 | 34,520 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines from scipy.sparse.csgraph import connected_components import numpy as np N = int(readline()) LS = np.array(read().split(), np.int32) L = LS[::2] S = LS[1::2] - 1 graph = np.zeros((N, N), np.bool_) graph[np.arange(N), S] = 1 Ncomp, comp = connected_components(graph, connection='strong') out_deg = [0] * Ncomp for i, s in enumerate(S): ci = comp[i] cs = comp[s] if ci == cs: continue out_deg[ci] += 1 answer = 0 for i in range(Ncomp): V = np.where(comp == i)[0] x = L[V].sum() y = L[V].min() if out_deg[i] == 0: x += y answer += x print(answer / 2)