#include <bits/stdc++.h>
using namespace std;
#define int long long
vector< vector<int> > Graph;
vector< vector< pair<int, int> > > minChildren;
const int INF = 1e15;
int dfs(int x, int last){
int mini = INF;
minChildren[x].clear();
for(int a : Graph[x]){
if(a == last) continue;
int b = dfs(a,x);
mini = min(mini, b);
minChildren[x].push_back(make_pair(b, a));
}
if(!Graph[x].size()){
return x;
}
//cout << "NODE " << x << ' ' << minChildren[x].size() << endl;
sort(minChildren[x].begin(), minChildren[x].end());
return min(x, mini);
}
vector< bool > isFull;
vector<int> priority;
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
int curr = 0;
vector< int> depth;
void add(int node, int d){
depth[node] = d;
for(auto a : minChildren[node]){
add(a.second,d+1);
}
priority[node] = curr++;
pq.push(make_pair(priority[node], node));
cout << node << endl;
}
vector< int > up;
int tot ;
vector< vector< int > > parents;
void calc(int n){
for(int i = 1; i<=n; i++){
parents[0][i] = up[i];
if(parents[0][i] == 0) parents[0][i] = -1;
}
for(int i = 1; i < 20; i++){
for(int j = 1; j <= n; j++){
if(parents[i-1][j] != -1)
parents[i][j] = parents[i-1][parents[i-1][j]];
else parents[i][j] = -1;
}
}
}
int ans(int x){
int s = depth[x];
int b = x;
for(int i = 19; i >= 0; i--){
if(parents[i][x] != -1 && isFull[parents[i][x]]){
x = parents[i][x];
}
}
int ar = depth[x];
int ans = s-ar;
if(ans != 0){
isFull[x] = false;
pq.push({priority[x],x});
isFull[b] = true;
}else{
pq.push({priority[b], b});
}
return ans;
}
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);
priority.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;
}
minChildren.resize(n+1);
depth.resize(n+1);
dfs(root,-1);
add(root,0);
isFull.resize(n+1);
parents.resize(20, vector<int>(n+1));
calc(n);
while(q--){
int a;
cin >> a;
int b;
cin >> b;
if(a == 1){
int last = 0;
for(int i = 0; i < b; i++){
last = pq.top().second;
isFull[last] = true;
pq.pop();
}
cout << last << endl;
}else{
isFull[b] = false;
cout << ans(b) << endl;
}
}
}
Compilation message
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:109:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
add(root,0);
~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Incorrect |
406 ms |
19920 KB |
Output isn't correct |
| 3 |
Incorrect |
381 ms |
20200 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 6 |
Incorrect |
6 ms |
640 KB |
Output isn't correct |
| 7 |
Incorrect |
8 ms |
640 KB |
Output isn't correct |
| 8 |
Incorrect |
9 ms |
640 KB |
Output isn't correct |
| 9 |
Incorrect |
24 ms |
1536 KB |
Output isn't correct |
| 10 |
Incorrect |
81 ms |
5496 KB |
Output isn't correct |
| 11 |
Incorrect |
433 ms |
19900 KB |
Output isn't correct |
| 12 |
Incorrect |
416 ms |
20336 KB |
Output isn't correct |
| 13 |
Incorrect |
444 ms |
20092 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
8564 KB |
Output isn't correct |
| 2 |
Incorrect |
583 ms |
36564 KB |
Output isn't correct |
| 3 |
Incorrect |
450 ms |
29996 KB |
Output isn't correct |
| 4 |
Incorrect |
244 ms |
11504 KB |
Output isn't correct |
| 5 |
Incorrect |
321 ms |
11376 KB |
Output isn't correct |
| 6 |
Incorrect |
268 ms |
11424 KB |
Output isn't correct |
| 7 |
Incorrect |
254 ms |
9696 KB |
Output isn't correct |
| 8 |
Incorrect |
189 ms |
8552 KB |
Output isn't correct |
| 9 |
Incorrect |
551 ms |
37096 KB |
Output isn't correct |
| 10 |
Incorrect |
578 ms |
36460 KB |
Output isn't correct |
| 11 |
Incorrect |
614 ms |
36476 KB |
Output isn't correct |
| 12 |
Incorrect |
591 ms |
33116 KB |
Output isn't correct |
| 13 |
Incorrect |
449 ms |
38696 KB |
Output isn't correct |
| 14 |
Incorrect |
412 ms |
30056 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
273 ms |
18876 KB |
Output isn't correct |
| 2 |
Incorrect |
608 ms |
33920 KB |
Output isn't correct |
| 3 |
Incorrect |
444 ms |
35052 KB |
Output isn't correct |
| 4 |
Incorrect |
424 ms |
29960 KB |
Output isn't correct |
| 5 |
Incorrect |
456 ms |
29416 KB |
Output isn't correct |
| 6 |
Incorrect |
411 ms |
29376 KB |
Output isn't correct |
| 7 |
Incorrect |
403 ms |
27112 KB |
Output isn't correct |
| 8 |
Incorrect |
516 ms |
35068 KB |
Output isn't correct |
| 9 |
Incorrect |
547 ms |
37196 KB |
Output isn't correct |
| 10 |
Incorrect |
635 ms |
36880 KB |
Output isn't correct |
| 11 |
Incorrect |
643 ms |
36716 KB |
Output isn't correct |
| 12 |
Incorrect |
598 ms |
33864 KB |
Output isn't correct |
| 13 |
Incorrect |
670 ms |
43892 KB |
Output isn't correct |
| 14 |
Incorrect |
548 ms |
30164 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
696 ms |
37340 KB |
Output isn't correct |
| 2 |
Incorrect |
654 ms |
34028 KB |
Output isn't correct |
| 3 |
Incorrect |
502 ms |
43624 KB |
Output isn't correct |
| 4 |
Incorrect |
651 ms |
37392 KB |
Output isn't correct |
| 5 |
Incorrect |
574 ms |
36716 KB |
Output isn't correct |
| 6 |
Incorrect |
541 ms |
36588 KB |
Output isn't correct |
| 7 |
Incorrect |
603 ms |
34000 KB |
Output isn't correct |
| 8 |
Incorrect |
476 ms |
43824 KB |
Output isn't correct |
| 9 |
Incorrect |
412 ms |
30052 KB |
Output isn't correct |
