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
AC × 1
AC × 31
AC × 61
AC × 96
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