Submission #751011

#	Time	Username	Problem	Language	Result	Execution time	Memory
751011		rahulverma	Poklon (COCI17_poklon7)	Java	78 / 120	1095 ms	262144 KiB

poklon

import java.io.*;
import java.util.*;
import java.math.*;
public class poklon {
	public static int[][] graph;
	public static BigInteger[] sub;
	public static boolean works = true;
	public static BigInteger[] 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 BigInteger[n];
		need = new BigInteger[n];
		for(int i = 0; i < n; i++) sub[i] = new BigInteger("0", 2);
		for(int i = 0; i < n; i++) need[i] = new BigInteger("0", 2);
		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);
		PrintWriter pw = new PrintWriter(System.out);
		pw.println((need[0].add(sub[0])).toString(2));
		pw.close();
		
	}
	public static void distribute(int node) {
		BigInteger sum1 = new BigInteger("0", 2);
		BigInteger sum2 = new BigInteger("0", 2);
		BigInteger sum3 = new BigInteger("0", 2);
		BigInteger sum4 = new BigInteger("0", 2);
		if(graph[node][0] > 0) {
			distribute(graph[node][0]);
			sum1 = sub[graph[node][0]].add(need[graph[node][0]]);
			sum3 = need[graph[node][0]];
		}
		else sum1 = new BigInteger(Integer.toBinaryString(-1*graph[node][0]), 2);
		if(graph[node][1] > 0) {
			distribute(graph[node][1]);
			sum2 = sub[graph[node][1]].add(need[graph[node][1]]);;
			sum4 = need[graph[node][1]];
		}
		else sum2 = new BigInteger(Integer.toBinaryString(-1*graph[node][1]), 2);
		need[node] = sum3.add(sum4);
		need[node] = need[node].add((sum1.subtract(sum2)).abs());
		
		
	}
	
	public static BigInteger dfs(int node) {
		if(graph[node][0] > 0) {
			sub[node] = sub[node].add(dfs(graph[node][0]));
		}
		else {
			sub[node] = sub[node].add(new BigInteger(Integer.toBinaryString(-1*graph[node][0]), 2));
		}
		if(graph[node][1] > 0) {
			sub[node] = sub[node].add(dfs(graph[node][1]));
		}
		else {
			sub[node] = sub[node].add(new BigInteger(Integer.toBinaryString(-1*graph[node][1]), 2));
		}
		return sub[node];
	}


}

• Subtask 1: 78 / 120