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];
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
8376 KB |
Output is correct |
| 2 |
Correct |
60 ms |
8392 KB |
Output is correct |
| 3 |
Correct |
62 ms |
8392 KB |
Output is correct |
| 4 |
Correct |
60 ms |
8564 KB |
Output is correct |
| 5 |
Correct |
64 ms |
8328 KB |
Output is correct |
| 6 |
Correct |
68 ms |
8684 KB |
Output is correct |
| 7 |
Correct |
79 ms |
8748 KB |
Output is correct |
| 8 |
Correct |
96 ms |
9700 KB |
Output is correct |
| 9 |
Correct |
110 ms |
9940 KB |
Output is correct |
| 10 |
Correct |
203 ms |
12664 KB |
Output is correct |
| 11 |
Correct |
387 ms |
19344 KB |
Output is correct |
| 12 |
Correct |
675 ms |
33716 KB |
Output is correct |
| 13 |
Execution timed out |
1069 ms |
95200 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1084 ms |
108944 KB |
Time limit exceeded |
| 15 |
Correct |
820 ms |
62012 KB |
Output is correct |
| 16 |
Execution timed out |
1077 ms |
129508 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1078 ms |
184644 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1095 ms |
184352 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1069 ms |
206520 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1086 ms |
262144 KB |
Time limit exceeded |
