oj.uz

답안 #751013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751013 2023-05-30T19:26:59 Z rahulverma Poklon (COCI17_poklon7) Java 11
78 / 120
 1000 ms 262144 KB 
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.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 8312 KB Output is correct
2 Correct 65 ms 8216 KB Output is correct
3 Correct 64 ms 8612 KB Output is correct
4 Correct 63 ms 8232 KB Output is correct
5 Correct 65 ms 8480 KB Output is correct
6 Correct 75 ms 8668 KB Output is correct
7 Correct 81 ms 8680 KB Output is correct
8 Correct 100 ms 9552 KB Output is correct
9 Correct 112 ms 9864 KB Output is correct
10 Correct 191 ms 12184 KB Output is correct
11 Correct 409 ms 19112 KB Output is correct
12 Correct 549 ms 22132 KB Output is correct
13 Execution timed out 1091 ms 107664 KB Time limit exceeded
14 Execution timed out 1082 ms 108568 KB Time limit exceeded
15 Correct 824 ms 61588 KB Output is correct
16 Execution timed out 1086 ms 116096 KB Time limit exceeded
17 Execution timed out 1068 ms 186100 KB Time limit exceeded
18 Execution timed out 1084 ms 186792 KB Time limit exceeded
19 Execution timed out 1096 ms 203964 KB Time limit exceeded
20 Execution timed out 1068 ms 262144 KB Time limit exceeded