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 |
68 ms |
8312 KB |
Output is correct |
| 2 |
Correct |
65 ms |
8216 KB |
Output is correct |
| 3 |
Correct |
64 ms |
8612 KB |
Output is correct |
| 4 |
Correct |
63 ms |
8232 KB |
Output is correct |
| 5 |
Correct |
65 ms |
8480 KB |
Output is correct |
| 6 |
Correct |
75 ms |
8668 KB |
Output is correct |
| 7 |
Correct |
81 ms |
8680 KB |
Output is correct |
| 8 |
Correct |
100 ms |
9552 KB |
Output is correct |
| 9 |
Correct |
112 ms |
9864 KB |
Output is correct |
| 10 |
Correct |
191 ms |
12184 KB |
Output is correct |
| 11 |
Correct |
409 ms |
19112 KB |
Output is correct |
| 12 |
Correct |
549 ms |
22132 KB |
Output is correct |
| 13 |
Execution timed out |
1091 ms |
107664 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1082 ms |
108568 KB |
Time limit exceeded |
| 15 |
Correct |
824 ms |
61588 KB |
Output is correct |
| 16 |
Execution timed out |
1086 ms |
116096 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1068 ms |
186100 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1084 ms |
186792 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1096 ms |
203964 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1068 ms |
262144 KB |
Time limit exceeded |
