#include <bits/stdc++.h>
using namespace std;
#define int long long
vector< vector<int> > Graph;
vector<int> minLeft;
vector<int> minRight;
const int INF = 1e15;
void dfs(int x, int last){
for(int a : Graph[x]){
if(a == last) continue;
dfs(a,x);
}
if(!Graph[x].size()){
minLeft[x] = INF;
minRight[x] = INF;
return;
}
minLeft[x] = min(min(minLeft[Graph[x][0]], minRight[Graph[x][0]]), Graph[x][0]);
minRight[x] = min(min(minRight[Graph[x][1]], minLeft[Graph[x][1]]), Graph[x][1]);
}
vector< bool > isFull;
int last;
void add(int node){
// cout << node << endl;
if(Graph[node].size() == 0 || (isFull[Graph[node][0]] && isFull[Graph[node][1]])){
isFull[node] = true;
last = node;
return;
}
if(isFull[Graph[node][1]]) add(Graph[node][0]);
else if(isFull[Graph[node][0]]) add(Graph[node][1]);
else if(minLeft[node] < minRight[node]){
add(Graph[node][0]);
}else{
add(Graph[node][1]);
}
}
vector< int > up;
int tot ;
void rem(int node, int last){
if(node == 0) return;
if(last != -1){
if(!isFull[last] && isFull[node]){
tot++;
isFull[last] = true;
isFull[node] = false;
}
}
rem(up[node], node);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
Graph.resize(n+1);
int root;
up.resize(n+1);
for(int i = 0; i < n; i++){
int a;
cin >> a;
Graph[a].push_back(i+1);
up[i+1] = a;
if(a == 0) root = i+1;
}
minRight.resize(n+1);
minLeft.resize(n+1);
dfs(root,-1);
isFull.resize(n+1);
while(q--){
int a;
cin >> a;
int b;
cin >> b;
if(a == 1){
for(int i = 0; i < b; i++){
add(root);
}
cout << last << endl;
}else{
isFull[b] = false;
tot = 0;
rem(b,-1);
cout << tot << endl;
}
}
}
Compilation message
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:93:20: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
add(root);
~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
238 ms |
4752 KB |
Output is correct |
| 3 |
Correct |
186 ms |
5024 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
18 ms |
640 KB |
Output is correct |
| 10 |
Correct |
64 ms |
1408 KB |
Output is correct |
| 11 |
Correct |
273 ms |
4728 KB |
Output is correct |
| 12 |
Correct |
208 ms |
5028 KB |
Output is correct |
| 13 |
Correct |
259 ms |
4904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1069 ms |
2688 KB |
Time limit exceeded |
| 2 |
Runtime error |
85 ms |
18936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
36 ms |
13168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
14 ms |
4864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
17 ms |
6016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Execution timed out |
1065 ms |
3072 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1069 ms |
2844 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1073 ms |
2688 KB |
Time limit exceeded |
| 9 |
Runtime error |
59 ms |
19704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
78 ms |
18780 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
50 ms |
16376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
62 ms |
16120 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Execution timed out |
1064 ms |
11384 KB |
Time limit exceeded |
| 14 |
Runtime error |
42 ms |
13040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
10020 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Execution timed out |
1074 ms |
8320 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1083 ms |
10488 KB |
Time limit exceeded |
| 4 |
Runtime error |
33 ms |
12152 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
52 ms |
15224 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
57 ms |
15224 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Execution timed out |
1080 ms |
6776 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1079 ms |
10332 KB |
Time limit exceeded |
| 9 |
Runtime error |
42 ms |
14972 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
44 ms |
14632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
72 ms |
18780 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Execution timed out |
1075 ms |
8312 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1066 ms |
12920 KB |
Time limit exceeded |
| 14 |
Runtime error |
33 ms |
13172 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
19576 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Execution timed out |
1082 ms |
8440 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1056 ms |
12920 KB |
Time limit exceeded |
| 4 |
Runtime error |
62 ms |
19676 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Execution timed out |
1077 ms |
9464 KB |
Time limit exceeded |
| 6 |
Runtime error |
64 ms |
15096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Execution timed out |
1034 ms |
8436 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1067 ms |
12920 KB |
Time limit exceeded |
| 9 |
Runtime error |
38 ms |
13168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
