#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n , q , A[N],B[N];
vector<int> adj[N] , v;
int P[N][20] , d[N] ,X[N];
int k,R;
void dfs(int u , int p){
P[u][0] = p;
for(int i = 1; i <= 18; ++i) P[u][i] = P[P[u][i- 1]][i- 1];
for(int v : adj[u]){
d[v] = d[u] + 1;
dfs(v,u);
}
v.emplace_back(u);
}
int F(int u){
for(int i = 17; ~i; --i){
int y= P[u][i];
if(X[y]==1) u = P[u][i];
}
return u;
}
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n>>q;
int a;
for(int i = 1; i<= n; ++i){
cin >> a;
if(a==0)R = i;
if(a)adj[a].emplace_back(i);
}
for(int i = 1; i <= n; ++i)sort(adj[i].begin() , adj[i].end());
dfs(R,0);
//for(int x : v)cout << x << " ";cout << endl;
for(int i = 0; i < v.size(); ++i) A[v[i]] = i+1 , B[i + 1] = v[i];
int t;
set<int> free;
for(int i= 1; i<= n; ++i)free.insert(i);
while(q--){
cin >> t;
if(t==1){
int k;
cin >>k;
int x;
for(int i = 0; i < k; ++i){
x = *free.begin();
X[B[x]] = 1;
free.erase(free.begin());
}
//cout << k << "k "<<endl;
cout << B[x] <<endl;
}else{
int h; cin >> h;
int v = F(h);
//cout << v << " v" << endl;
// cout << v << "v"<<endl;
free.insert(A[v]);
X[v]=0;
cout << d[h] - d[v]<<endl;
}
}
}
Compilation message
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i = 0; i < v.size(); ++i) A[v[i]] = i+1 , B[i + 1] = v[i];
| ~~^~~~~~~~~~
ballmachine.cpp:53:24: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
53 | cout << B[x] <<endl;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Execution timed out |
1089 ms |
14376 KB |
Time limit exceeded |
| 3 |
Incorrect |
181 ms |
14748 KB |
Output isn't correct |
| 4 |
Execution timed out |
1087 ms |
2636 KB |
Time limit exceeded |
| 5 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
2764 KB |
Output isn't correct |
| 7 |
Execution timed out |
1085 ms |
2764 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1092 ms |
2764 KB |
Time limit exceeded |
| 9 |
Incorrect |
16 ms |
3324 KB |
Output isn't correct |
| 10 |
Execution timed out |
1082 ms |
5808 KB |
Time limit exceeded |
| 11 |
Incorrect |
225 ms |
14524 KB |
Output isn't correct |
| 12 |
Incorrect |
176 ms |
14472 KB |
Output isn't correct |
| 13 |
Incorrect |
209 ms |
14536 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
7472 KB |
Output is correct |
| 2 |
Incorrect |
304 ms |
23044 KB |
Output isn't correct |
| 3 |
Incorrect |
206 ms |
19848 KB |
Output isn't correct |
| 4 |
Execution timed out |
1082 ms |
9028 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1079 ms |
8696 KB |
Time limit exceeded |
| 6 |
Incorrect |
171 ms |
9284 KB |
Output isn't correct |
| 7 |
Incorrect |
208 ms |
8460 KB |
Output isn't correct |
| 8 |
Correct |
125 ms |
7448 KB |
Output is correct |
| 9 |
Incorrect |
291 ms |
23292 KB |
Output isn't correct |
| 10 |
Incorrect |
309 ms |
23180 KB |
Output isn't correct |
| 11 |
Incorrect |
250 ms |
22996 KB |
Output isn't correct |
| 12 |
Incorrect |
273 ms |
21504 KB |
Output isn't correct |
| 13 |
Correct |
208 ms |
23420 KB |
Output is correct |
| 14 |
Incorrect |
188 ms |
19780 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
13072 KB |
Output isn't correct |
| 2 |
Incorrect |
300 ms |
21852 KB |
Output isn't correct |
| 3 |
Correct |
196 ms |
21940 KB |
Output is correct |
| 4 |
Incorrect |
176 ms |
19168 KB |
Output isn't correct |
| 5 |
Incorrect |
183 ms |
18752 KB |
Output isn't correct |
| 6 |
Incorrect |
189 ms |
18744 KB |
Output isn't correct |
| 7 |
Incorrect |
189 ms |
17840 KB |
Output isn't correct |
| 8 |
Correct |
184 ms |
21744 KB |
Output is correct |
| 9 |
Incorrect |
289 ms |
23488 KB |
Output isn't correct |
| 10 |
Incorrect |
290 ms |
23080 KB |
Output isn't correct |
| 11 |
Incorrect |
288 ms |
23100 KB |
Output isn't correct |
| 12 |
Incorrect |
307 ms |
21956 KB |
Output isn't correct |
| 13 |
Correct |
292 ms |
26820 KB |
Output is correct |
| 14 |
Incorrect |
242 ms |
20028 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
287 ms |
23492 KB |
Output isn't correct |
| 2 |
Incorrect |
298 ms |
21920 KB |
Output isn't correct |
| 3 |
Correct |
232 ms |
26204 KB |
Output is correct |
| 4 |
Incorrect |
268 ms |
23468 KB |
Output isn't correct |
| 5 |
Incorrect |
280 ms |
23096 KB |
Output isn't correct |
| 6 |
Incorrect |
259 ms |
23060 KB |
Output isn't correct |
| 7 |
Incorrect |
292 ms |
21824 KB |
Output isn't correct |
| 8 |
Correct |
225 ms |
26168 KB |
Output is correct |
| 9 |
Incorrect |
187 ms |
19652 KB |
Output isn't correct |
