結果
問題 | No.19 ステージの選択 |
ユーザー | Grenache |
提出日時 | 2016-06-21 20:52:53 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 151 ms / 5,000 ms |
コード長 | 2,827 bytes |
コンパイル時間 | 4,572 ms |
コンパイル使用メモリ | 80,508 KB |
実行使用メモリ | 58,072 KB |
最終ジャッジ日時 | 2023-08-24 23:31:04 |
合計ジャッジ時間 | 8,050 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 130 ms
56,156 KB |
testcase_01 | AC | 126 ms
55,912 KB |
testcase_02 | AC | 126 ms
56,292 KB |
testcase_03 | AC | 127 ms
55,540 KB |
testcase_04 | AC | 146 ms
55,884 KB |
testcase_05 | AC | 147 ms
55,876 KB |
testcase_06 | AC | 151 ms
55,712 KB |
testcase_07 | AC | 148 ms
56,212 KB |
testcase_08 | AC | 149 ms
56,248 KB |
testcase_09 | AC | 147 ms
54,232 KB |
testcase_10 | AC | 131 ms
56,032 KB |
testcase_11 | AC | 126 ms
55,716 KB |
testcase_12 | AC | 127 ms
56,112 KB |
testcase_13 | AC | 127 ms
55,812 KB |
testcase_14 | AC | 132 ms
54,144 KB |
testcase_15 | AC | 135 ms
55,912 KB |
testcase_16 | AC | 143 ms
55,648 KB |
testcase_17 | AC | 135 ms
56,120 KB |
testcase_18 | AC | 147 ms
58,072 KB |
testcase_19 | AC | 136 ms
56,236 KB |
testcase_20 | AC | 131 ms
56,068 KB |
testcase_21 | AC | 137 ms
56,216 KB |
testcase_22 | AC | 136 ms
55,992 KB |
testcase_23 | AC | 142 ms
55,864 KB |
ソースコード
import java.util.*; public class Main_yukicoder19 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); UnionFind uf = new UnionFind(n); List<List<Integer>> edges = new ArrayList<>(n); for (int i = 0; i < n; i++) { edges.add(new ArrayList<>()); } int[] l = new int[n]; for (int i = 0; i < n; i++) { l[i] = sc.nextInt(); int s = sc.nextInt() - 1; uf.unite(i, s); edges.get(s).add(i); } Map<Integer, Double> hm = new HashMap<>(); for (int i = 0; i < n; i++) { double tmp = dfs(i, uf.count(i), l, edges); if (hm.containsKey(uf.find(i))) { hm.put(uf.find(i), Math.min(hm.get(uf.find(i)), tmp)); } else { hm.put(uf.find(i), tmp); } } double ret = 0; for (double e : hm.values()) { ret += e; } System.out.printf("%.1f\n", ret); sc.close(); } private static double dfs(int v, int count, int[] l, List<List<Integer>> edges) { double ret = 0; int cnt = 0; Queue<Integer> q = new ArrayDeque<>(); q.add(v); ret += l[v]; cnt++; boolean[] used = new boolean[l.length]; used[v] = true; while (!q.isEmpty()) { int e = q.remove(); for (int nv : edges.get(e)) { if (!used[nv]) { ret += (double)l[nv] / 2; cnt++; used[nv] = true; q.add(nv); } } } if (cnt == count) { return ret; } else { return Double.MAX_VALUE; } } @SuppressWarnings("unused") private static class UnionFind { int n; // cnt : 異なる集合の数 int cnt; // parent[x] : 0~n-1 の場合、要素xのroot要素 // : -1~-n の場合、自分自身がroot要素、 // -parent[x]でxを含む集合の要素数 int[] parent; UnionFind(int n) { this.n = n; cnt = n; parent = new int[n]; Arrays.fill(parent, -1); } // xのrootを求める int find(int x) { if (parent[x] < 0) { return x; } else { return parent[x] = find(parent[x]); } } // xとyが同じ集合に属するのか boolean same(int x, int y) { return find(x) == find(y); } // xとyの属する集合を併合する void unite(int x, int y) { x = find(x); y = find(y); if (x == y) { return; } cnt--; // 要素数が大きい集合をrootにする(Quick Find Weighted?) if (parent[x] > parent[y]) { parent[y] += parent[x]; parent[x] = y; } else { parent[x] += parent[y]; parent[y] = x; } return; } // 要素xを含む集合の要素数 int count(int x) { return -parent[find(x)]; } // 異なる集合の数 int count() { return cnt; } } }