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);
System.out.println((need[0].add(sub[0])).toString(2));
}
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));
System.out.println("HI" + node + " " + sub[node].toString(10));
}
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];
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
11180 KB |
Output isn't correct |
| 2 |
Incorrect |
115 ms |
10672 KB |
Output isn't correct |
| 3 |
Incorrect |
123 ms |
10732 KB |
Output isn't correct |
| 4 |
Incorrect |
117 ms |
10692 KB |
Output isn't correct |
| 5 |
Incorrect |
128 ms |
10488 KB |
Output isn't correct |
| 6 |
Incorrect |
144 ms |
10568 KB |
Output isn't correct |
| 7 |
Incorrect |
137 ms |
10816 KB |
Output isn't correct |
| 8 |
Incorrect |
166 ms |
11288 KB |
Output isn't correct |
| 9 |
Incorrect |
181 ms |
11304 KB |
Output isn't correct |
| 10 |
Incorrect |
281 ms |
14748 KB |
Output isn't correct |
| 11 |
Incorrect |
730 ms |
20296 KB |
Output isn't correct |
| 12 |
Execution timed out |
1073 ms |
28508 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1090 ms |
72756 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1077 ms |
82716 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1072 ms |
46408 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1059 ms |
91368 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1058 ms |
175888 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1066 ms |
177576 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1028 ms |
209832 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1075 ms |
262144 KB |
Time limit exceeded |
