Submission #691266
Source Code Expand
import java.util.*; public class Main { void solve() { try(final Scanner sc = new Scanner(System.in)) { int n = sc.nextInt(); long[] w = new long[n]; for(int i = 0; i < n; i++) { w[i] = sc.nextLong(); } System.out.println(new HuTucker(w).getCost()); } } public static void main(String[] args) { new Main().solve(); } static public class HuTucker { long[] w; int[] depth; long ans; AdjListGraph g; LeftistHeap<HpqNode> merge(int[] l, int[] r, int li, int ri, long[] val, LeftistHeap<HpqNode>[] hpq, MpqNode mn) { if(r[ri] < l.length) l[r[ri]] = li; r[li] = r[ri]; hpq[li].meld(hpq[ri]); hpq[ri] = null; val[ri] = Long.MIN_VALUE; mn.idx = li; return hpq[li]; } public HuTucker(long[] w) { int n = w.length; PriorityQueue<MpqNode> mpq = new PriorityQueue<MpqNode>(); this.w = w; AdjListGraph g = new AdjListGraph(2 * w.length - 1, 2 * w.length - 2); int[] left = new int[n - 1]; int[] right = new int[n - 1]; long[] val = new long[n - 1]; LeftistHeap<HpqNode>[] hpq = new LeftistHeap[n - 1]; boolean[] merged = new boolean[2 * n - 1]; for(int i = 0; i < n - 1; i++) { left[i] = i - 1; right[i] = i + 1; } for(int i = 0; i < n - 1; i++) { LeftistHeap<HpqNode> h = new LeftistHeap<HpqNode>(); long sum = 0; for(int j = 0; j < 2; j++) { h.push(new HpqNode(w[i + j], i + j)); sum += w[i + j]; } hpq[i] = h; val[i] = sum; mpq.add(new MpqNode(sum, i)); } for(int i = 0, j = n; i < n - 1; i++) { while(true) { MpqNode mn = mpq.poll(); if(val[mn.idx] != mn.w) { continue; } LeftistHeap<HpqNode> h = hpq[mn.idx]; HpqNode t1 = h.pop(); HpqNode t2 = h.pop(); if(!merged[t1.idx] && !merged[t2.idx]) { merged[t1.idx] = merged[t2.idx] = true; h.push(new HpqNode(t1.w + t2.w, j)); for(HpqNode t : new HpqNode[] { t1, t2, }) { g.addEdge(j, t.idx); if(t.idx >= n) continue; if(left[mn.idx] >= 0 && right[left[mn.idx]] == t.idx) { h = merge(left, right, left[mn.idx], mn.idx, val, hpq, mn); } if(right[mn.idx] < n - 1 && right[mn.idx] == t.idx) { h = merge(left, right, mn.idx, right[mn.idx], val, hpq, mn); } } j++; if (i != n - 2) { val[mn.idx] = hpq[mn.idx].top().w + hpq[mn.idx].top2nd().w; mn.w = val[mn.idx]; mpq.add(mn); } break; } if(!merged[t1.idx]) { h.push(t1); } else if(!merged[t2.idx]) { h.push(t2); } mn.w = h.top().w + h.top2nd().w; val[mn.idx] = mn.w; mpq.add(mn); } } depth = calcDepth(g, 2 * w.length - 2); ans = getCost(); } long getCost() { long ret = 0; for(int i = 0; i < w.length; i++) { ret += w[i] * depth[i]; } return ret; } int[] calcDepth(AdjListGraph g, int root) { int sp = 0; int[] depth = new int[g.V]; final int[] st = new int[g.V]; final boolean[] vis = new boolean[g.V]; st[sp++] = root; while(sp != 0) { final int v = st[--sp]; vis[v] = true; for(int e = g.head[v]; e != -1; e = g.next[e]) { final int to = g.to[e]; if(!vis[to]) { st[sp++] = to; depth[to] = depth[v] + 1; } } } return depth; } static class MpqNode implements Comparable<MpqNode> { long w; int idx; public MpqNode(long sum, int i) { w = sum; idx = i; } @Override public int compareTo(MpqNode o) { return Long.compare(w, o.w); } } static class HpqNode implements Comparable<HpqNode> { long w; int idx; public HpqNode(long v, int i) { w = v; idx = i; } @Override public int compareTo(HpqNode o) { return Long.compare(w, o.w); } } static public class LeftistHeap<T extends Comparable<T>> { private LeftistHeapNode<T> root; public void push(T x) { final LeftistHeapNode<T> n = new LeftistHeapNode<T>(x); if(root == null) { root = n; } else { root = LeftistHeapNode.meld(root, n); } } public T top() { return root.val; } public T top2nd() { if(root.r == null || root.l.val.compareTo(root.r.val) <= 0) { return root.l.val; } return root.r.val; } public T pop() { final T ret = root.val; root = LeftistHeapNode.meld(root.l, root.r); return ret; } public void meld(final LeftistHeap<T> heap) { if(root == null) { root = heap.root; } else { root = LeftistHeapNode.meld(root, heap.root); } } public boolean isEmpty() { return root == null; } private static class LeftistHeapNode<T extends Comparable<T>> { private LeftistHeapNode<T> l, r; private int s; private T val; private LeftistHeapNode(T x) { val = x; s = 1; } public static <T extends Comparable<T>> LeftistHeapNode<T> meld(LeftistHeapNode<T> a, LeftistHeapNode<T> b) { if(a == null) return b; if(b == null) return a; if(a.val.compareTo(b.val) > 0) { final LeftistHeapNode<T> t = a; a = b; b = t; } a.r = meld(a.r, b); if(a.l == null || a.l.s < a.r.s) { final LeftistHeapNode<T> t = a.l; a.l = a.r; a.r = t; } a.s = (a.r == null ? 0 : a.r.s) + 1; return a; } } } static class AdjListGraph { int m, V, E; int[] head, next, from, to, size; public AdjListGraph(int V, int E) { head = new int[V]; size = new int[V]; next = new int[E]; from = new int[E]; to = new int[E]; this.V = V; this.E = E; clear(); } public void clear(int v) { m = 0; for(int i = 0; i < v; i++) { head[i] = -1; } } public void clear() { m = 0; Arrays.fill(head, -1); Arrays.fill(size, 0); } public void addEdge(int s, int t) { next[m] = head[s]; head[s] = m; from[m] = s; to[m++] = t; size[s]++; } } } }
Submission Info
Submission Time | |
---|---|
Task | C - 最適二分探索木 |
User | tanzaku |
Language | Java8 (OpenJDK 1.8.0) |
Score | 101 |
Code Size | 6327 Byte |
Status | AC |
Exec Time | 1343 ms |
Memory | 58356 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | 1 / 1 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt |
Dataset1 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt |
Dataset2 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt |
Dataset3 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt, 03_00.txt, 03_01.txt, 03_02.txt, 03_03.txt, 03_04.txt, 03_05.txt, 03_06.txt, 03_07.txt, 03_08.txt, 03_09.txt, 03_10.txt, 03_11.txt, 03_12.txt, 03_13.txt, 03_14.txt, 03_15.txt, 03_16.txt, 03_17.txt, 03_18.txt, 03_19.txt, 03_20.txt, 03_21.txt, 03_22.txt, 03_23.txt, 03_24.txt, 03_25.txt, 03_26.txt, 03_27.txt, 03_28.txt, 03_29.txt, 03_30.txt, 03_31.txt, 03_32.txt, 03_33.txt, 03_34.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 207 ms | 10068 KB |
01_00.txt | AC | 202 ms | 9684 KB |
01_01.txt | AC | 210 ms | 9676 KB |
01_02.txt | AC | 214 ms | 9684 KB |
01_03.txt | AC | 214 ms | 9680 KB |
01_04.txt | AC | 215 ms | 9684 KB |
01_05.txt | AC | 218 ms | 9684 KB |
01_06.txt | AC | 222 ms | 9556 KB |
01_07.txt | AC | 218 ms | 9800 KB |
01_08.txt | AC | 211 ms | 9680 KB |
01_09.txt | AC | 210 ms | 9680 KB |
01_10.txt | AC | 211 ms | 9556 KB |
01_11.txt | AC | 308 ms | 9676 KB |
01_12.txt | AC | 206 ms | 9680 KB |
01_13.txt | AC | 211 ms | 9552 KB |
01_14.txt | AC | 210 ms | 9676 KB |
01_15.txt | AC | 211 ms | 9676 KB |
01_16.txt | AC | 206 ms | 9680 KB |
01_17.txt | AC | 203 ms | 9676 KB |
01_18.txt | AC | 204 ms | 9556 KB |
01_19.txt | AC | 202 ms | 9548 KB |
01_20.txt | AC | 208 ms | 9680 KB |
01_21.txt | AC | 206 ms | 9680 KB |
01_22.txt | AC | 210 ms | 9676 KB |
01_23.txt | AC | 218 ms | 9672 KB |
01_24.txt | AC | 206 ms | 9684 KB |
01_25.txt | AC | 206 ms | 9676 KB |
01_26.txt | AC | 206 ms | 9556 KB |
01_27.txt | AC | 211 ms | 9684 KB |
01_28.txt | AC | 210 ms | 9552 KB |
01_29.txt | AC | 210 ms | 9684 KB |
02_00.txt | AC | 294 ms | 14996 KB |
02_01.txt | AC | 375 ms | 15160 KB |
02_02.txt | AC | 291 ms | 15248 KB |
02_03.txt | AC | 286 ms | 15184 KB |
02_04.txt | AC | 282 ms | 15140 KB |
02_05.txt | AC | 298 ms | 15364 KB |
02_06.txt | AC | 298 ms | 15284 KB |
02_07.txt | AC | 307 ms | 15196 KB |
02_08.txt | AC | 302 ms | 14908 KB |
02_09.txt | AC | 284 ms | 15136 KB |
02_10.txt | AC | 287 ms | 15160 KB |
02_11.txt | AC | 353 ms | 14936 KB |
02_12.txt | AC | 293 ms | 15468 KB |
02_13.txt | AC | 302 ms | 15072 KB |
02_14.txt | AC | 302 ms | 15464 KB |
02_15.txt | AC | 302 ms | 14716 KB |
02_16.txt | AC | 306 ms | 15332 KB |
02_17.txt | AC | 302 ms | 15164 KB |
02_18.txt | AC | 294 ms | 15076 KB |
02_19.txt | AC | 305 ms | 15344 KB |
02_20.txt | AC | 306 ms | 15344 KB |
02_21.txt | AC | 302 ms | 15040 KB |
02_22.txt | AC | 295 ms | 15408 KB |
02_23.txt | AC | 278 ms | 14840 KB |
02_24.txt | AC | 294 ms | 15140 KB |
02_25.txt | AC | 294 ms | 15252 KB |
02_26.txt | AC | 391 ms | 15192 KB |
02_27.txt | AC | 318 ms | 15280 KB |
02_28.txt | AC | 305 ms | 15008 KB |
02_29.txt | AC | 283 ms | 14704 KB |
03_00.txt | AC | 1102 ms | 52456 KB |
03_01.txt | AC | 1078 ms | 48164 KB |
03_02.txt | AC | 1131 ms | 51192 KB |
03_03.txt | AC | 1130 ms | 50808 KB |
03_04.txt | AC | 1170 ms | 56264 KB |
03_05.txt | AC | 970 ms | 49852 KB |
03_06.txt | AC | 1062 ms | 49304 KB |
03_07.txt | AC | 1034 ms | 49024 KB |
03_08.txt | AC | 1086 ms | 48688 KB |
03_09.txt | AC | 991 ms | 53744 KB |
03_10.txt | AC | 1055 ms | 47992 KB |
03_11.txt | AC | 1111 ms | 46636 KB |
03_12.txt | AC | 1169 ms | 52320 KB |
03_13.txt | AC | 1343 ms | 48736 KB |
03_14.txt | AC | 1053 ms | 53272 KB |
03_15.txt | AC | 1073 ms | 51392 KB |
03_16.txt | AC | 1010 ms | 51980 KB |
03_17.txt | AC | 1114 ms | 49000 KB |
03_18.txt | AC | 1002 ms | 48740 KB |
03_19.txt | AC | 1110 ms | 48840 KB |
03_20.txt | AC | 1038 ms | 51088 KB |
03_21.txt | AC | 1186 ms | 58356 KB |
03_22.txt | AC | 1006 ms | 48992 KB |
03_23.txt | AC | 1054 ms | 50696 KB |
03_24.txt | AC | 1054 ms | 51556 KB |
03_25.txt | AC | 1066 ms | 52328 KB |
03_26.txt | AC | 1190 ms | 55900 KB |
03_27.txt | AC | 1142 ms | 51540 KB |
03_28.txt | AC | 966 ms | 48836 KB |
03_29.txt | AC | 1086 ms | 48284 KB |
03_30.txt | AC | 1110 ms | 49292 KB |
03_31.txt | AC | 1070 ms | 48704 KB |
03_32.txt | AC | 1138 ms | 53480 KB |
03_33.txt | AC | 1070 ms | 49540 KB |
03_34.txt | AC | 1030 ms | 49344 KB |