제출 #750533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
750533		rahulverma	Poklon (COCI17_poklon7)	Java	0 / 120	715 ms	123216 KiB

poklon

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

public class poklon {
	public static int[][] graph;
	public static long[] sub;
	public static boolean works;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		graph = new int[n][2];
		sub = new long[n];
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			graph[i][0] = Integer.parseInt(st.nextToken());
			graph[i][1] = Integer.parseInt(st.nextToken());
			if(graph[i][0] > 0) graph[i][0] -= 1;
			if(graph[i][1] > 0) graph[i][1] -= 1;
		}
		
		dfs(0);
		//for(long a: sub) System.out.println(a);
		
		long left = 0;
		long right = Long.MAX_VALUE;
		//distribute(0, 24);
		while(left < right) {
			long mid = left + (right - left) / 2;
			works = true;
			distribute(0, mid);
			if(works) {
				right = mid;
			}
			else {
				left = mid + 1;
			}
		}
		long ans = left + sub[0];
		System.out.println(Long.toBinaryString(ans));
	}
	public static void distribute(int node, long cur) {
		long sum1 = 0;
		long sum2 = 0;
		if(graph[node][0] > 0) sum1 = sub[graph[node][0]];
		else sum1 = -1*graph[node][0];
		if(graph[node][1] > 0) sum2 = sub[graph[node][1]];
		else sum2 = -1*graph[node][1];
		
		// need to accurately fix return weights amount and break check
		if(cur < Math.abs(sum1 - sum2)) {
			works = false;
			return;
		}
		if(graph[node][0] > 0) {
			distribute(graph[node][0], sendV1(sum1, sum2, cur));
		}
		if(graph[node][1] > 0) distribute(graph[node][1], sendV1(sum2, sum1, cur));
		
	}
	
	public static long dfs(int node) {
		if(graph[node][0] > 0) sub[node] += dfs(graph[node][0]);
		else sub[node] += -1*graph[node][0];
		if(graph[node][1] > 0) sub[node] += dfs(graph[node][1]);
		else sub[node] += -1*graph[node][1];
		return sub[node];
	}
	public static long sendV1(long v1, long v2, long total) {
		if(v1 > v2) return (total/2) - (v1 - v2)/2;
		return ((total+1)/2) + (v2 - v1)/2;
		// this is wrong
	}

}

• Subtask 1: 0 / 120