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
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
