답안 #750646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750646 2023-05-30T04:52:08 Z rahulverma Poklon (COCI17_poklon7) Java 11
48 / 120
1000 ms 131360 KB
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
	}

}
# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 8612 KB Output is correct
2 Correct 61 ms 8476 KB Output is correct
3 Correct 60 ms 8168 KB Output is correct
4 Correct 65 ms 8460 KB Output is correct
5 Correct 66 ms 8220 KB Output is correct
6 Correct 62 ms 8472 KB Output is correct
7 Correct 64 ms 8264 KB Output is correct
8 Correct 74 ms 8364 KB Output is correct
9 Incorrect 78 ms 8428 KB Output isn't correct
10 Incorrect 138 ms 11280 KB Output isn't correct
11 Incorrect 228 ms 14656 KB Output isn't correct
12 Incorrect 284 ms 15324 KB Output isn't correct
13 Incorrect 270 ms 18828 KB Output isn't correct
14 Incorrect 288 ms 23244 KB Output isn't correct
15 Incorrect 285 ms 20464 KB Output isn't correct
16 Incorrect 404 ms 46848 KB Output isn't correct
17 Incorrect 632 ms 91256 KB Output isn't correct
18 Incorrect 631 ms 93956 KB Output isn't correct
19 Incorrect 770 ms 99628 KB Output isn't correct
20 Execution timed out 1063 ms 131360 KB Time limit exceeded