제출 #384141

#제출 시각아이디문제언어결과실행 시간메모리
384141dapigNetwork (BOI15_net)Java
63 / 100
2079 ms116700 KiB
//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]); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...