oj.uz

답안 #750533

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750533 2023-05-29T16:14:59 Z rahulverma Poklon (COCI17_poklon7) Java 11
0 / 120
 715 ms 123216 KB 
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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 8668 KB Output isn't correct
2 Incorrect 72 ms 8272 KB Output isn't correct
3 Incorrect 66 ms 8288 KB Output isn't correct
4 Incorrect 59 ms 8372 KB Output isn't correct
5 Incorrect 68 ms 8308 KB Output isn't correct
6 Incorrect 63 ms 8456 KB Output isn't correct
7 Incorrect 66 ms 8448 KB Output isn't correct
8 Incorrect 90 ms 10564 KB Output isn't correct
9 Incorrect 79 ms 8312 KB Output isn't correct
10 Incorrect 138 ms 11168 KB Output isn't correct
11 Incorrect 217 ms 14736 KB Output isn't correct
12 Incorrect 276 ms 14876 KB Output isn't correct
13 Incorrect 260 ms 17976 KB Output isn't correct
14 Incorrect 277 ms 21660 KB Output isn't correct
15 Incorrect 294 ms 19508 KB Output isn't correct
16 Incorrect 377 ms 42828 KB Output isn't correct
17 Incorrect 602 ms 82868 KB Output isn't correct
18 Incorrect 614 ms 85180 KB Output isn't correct
19 Incorrect 715 ms 90524 KB Output isn't correct
20 Incorrect 681 ms 123216 KB Output isn't correct