Submission #384141

#	Time	Username	Problem	Language	Result	Execution time	Memory
384141		dapig	Network (BOI15_net)	Java	63 / 100	2079 ms	116700 KiB

net

//package week4;

import java.io.*;
import java.util.*;

public class net {

	public static void main(String[] args) throws IOException {

		net obj = new net();

		obj.doStuff();

	}

	int n;
	ArrayList<Integer>[] graph;
	int start;
	
	int[] bit;
	void upd(int n, int inc) {
		n++;
		while (n < bit.length) {
			bit[n] += inc;
			n += (n&-n);
		}
	}
	int find(int n) {
		int s = 0;
		n++;
		while (n > 0) {
			s += bit[n];
			n -= (n&-n);
		}
		return s;
	}
	int findfirst(int n) {
		if (graph[n].size()==1) return etrev[n];
		int l = 0, r = et.length, v = find(etrev[n]);
		int best = et.length-1;
		while (l < r) {
			int m = (l+r)/2;
			if (find(m) > v) {
				best = m; r = m;
			} else l = m+1;
		}
		return best;
	}
	
	int[] leaves;
	int[] et; int count = 0;
	int[] etrev;
	int leaf(int n, int p) {
		et[count] = n; count++;
		etrev[et[count-1]] = count-1;
		int vis = 0;
		for (int i : graph[n]) {
			if (i == p) continue;
			vis += leaf(i, n);
		}
		if (vis == 0) {
			leaves[n] = 1;
			upd(count-1, 1);
			return 1;
		}
		leaves[n] = vis;
		return vis;
	}
	
	class SortArr implements Comparator<int[]> {

		@Override
		public int compare(int[] o1, int[] o2) {
			return o2[1]-o1[1];
		}
		
	}
	
	ArrayList<int[]> pairs = new ArrayList<>();
	void process(int n, int p, int reps) {
		int max = 0, pos = 0, sum = 0;
		for (int i : graph[n]) {
			if (i == p) continue;
			sum += leaves[i];
			if (leaves[i] > max) {
				max = leaves[i];
				pos = i;
			}
		}
		int pairable = Math.min(sum, (sum-max)*2);
		if (reps > pairable) {
			process(pos, n, reps-pairable);
			leaves[pos] = sum-max;
			reps -= (reps-pairable);
		}
		/*
		PriorityQueue<int[]> pq = new PriorityQueue<>(new SortArr());
		for (int i : graph[n]) {
			if (i == p) continue;
			pq.add(new int[] {i, leaves[i]});
		}
		
		while (reps > 1) {
			int[] data1 = pq.poll();
			int[] data2 = pq.poll();
			int pos1 = findfirst(data1[0]);
			int pos2 = findfirst(data2[0]);
			upd(pos1, -1); upd(pos2, -1);
			pairs.add(new int[] {et[pos1]+1, et[pos2]+1});
			if (data1[1] > 1) pq.add(new int[] {data1[0], data1[1]-1});
			if (data2[1] > 1) pq.add(new int[] {data2[0], data2[1]-1});
			reps -= 2;
		}
		
		if (reps == 1) {
			int[] data1 = pq.poll();
			int pos1 = findfirst(data1[0]);
			upd(pos1, -1);
			pairs.add(new int[] {et[pos1]+1, n+1});
		}*/
		int maxleaves = 0;
		for (int i : graph[n]) {
			if (i==p) continue;
			maxleaves = Math.max(maxleaves, leaves[i]);
		}
		@SuppressWarnings("unchecked")
		Stack<Integer>[] stack = new Stack[maxleaves+1];
		for (int i = 0; i < stack.length; i++) {
			stack[i] = new Stack<>();
		}
		max = 0; int max2 = 0;
		for (int i : graph[n]) {
			if (i==p) continue;
			stack[leaves[i]].push(i);
			if (leaves[i] > max) {
				max2 = max; max = leaves[i];
			} else if (leaves[i] > max2) max2 = leaves[i];
		}
		while (reps > 1) {
			int[] data1 = new int[] {stack[max].pop(), max};
			int[] data2 = new int[] {stack[max2].pop(), max2};
			int pos1 = findfirst(data1[0]);
			int pos2 = findfirst(data2[0]);
			upd(pos1, -1); upd(pos2, -1);
			pairs.add(new int[] {et[pos1]+1, et[pos2]+1});
			if (data1[1] > 1) {
				stack[data1[1]-1].push(data1[0]);
			}
			if (data2[1] > 1) {
				stack[data2[1]-1].push(data2[0]);
			}
			if (stack[max].size() == 0) max--;
			if (stack[max2].size() == 0) max2--;
			if (max2 == max && stack[max].size() == 1) max2--;
			reps -= 2;
		}
		if (reps == 1) {
			int[] data1 = new int[] {stack[max].pop(), max};
			int pos1 = findfirst(data1[0]);
			upd(pos1, -1);
			pairs.add(new int[] {et[pos1]+1, n+1});
		}
	}
	
	@SuppressWarnings("unchecked")
	private void doStuff() throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		graph = new ArrayList[n];
		for (int i = 0; i < graph.length; i++) {
			graph[i] = new ArrayList<>();
		}
		for (int i = 0; i < graph.length-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			graph[a].add(b);
			graph[b].add(a);
		}
		br.close();
		
		for (int i = 0; i < graph.length; i++) {
			if (graph[i].size() > 1) {
				start = i; break;
			}
		}
		leaves = new int[graph.length];
		et = new int[graph.length];
		etrev = new int[graph.length];
		bit = new int[graph.length+1];
		leaf(start, -1);
		process(start, -1, leaves[start]);
		System.out.println(pairs.size());
		for (int[] i : pairs) {
			System.out.println(i[0]+" "+i[1]);
		}

	}

}

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 0 / 37