제출 #750646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
750646		rahulverma	Poklon (COCI17_poklon7)	Java	48 / 120	1063 ms	131360 KiB

poklon

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

public class poklon {
	public static int[][] graph;
	public static long[] sub;
	public static boolean works = true;
	public static long[] need;
	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];
		need = 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);
		distribute(0);
		System.out.println(Long.toBinaryString(need[0] + sub[0]));
		
	}
	public static void distribute(int node) {
		long sum1 = 0;
		long sum2 = 0;
		long sum3 = 0;
		long sum4 = 0;
		if(graph[node][0] > 0) {
			distribute(graph[node][0]);
			sum1 = sub[graph[node][0]] + need[graph[node][0]];
			sum3 = need[graph[node][0]];
		}
		else sum1 = -1*graph[node][0];
		if(graph[node][1] > 0) {
			distribute(graph[node][1]);
			sum2 = sub[graph[node][1]] + need[graph[node][1]];
			sum4 = need[graph[node][1]];
		}
		else sum2 = -1*graph[node][1];
		need[node] = sum3 + sum4 + Math.abs(sum1 - sum2);
		
		
	}
	
	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: 48 / 120