#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 = 18; ~i; --i){
int y= P[u][i];
if(X[y]) u = y;
}
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){
if(free.begin()==free.end())break;
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:54:24: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
54 | cout << B[x] <<endl;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Incorrect |
217 ms |
13400 KB |
Output isn't correct |
| 3 |
Incorrect |
178 ms |
13504 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
2764 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
2764 KB |
Output isn't correct |
| 8 |
Incorrect |
4 ms |
2764 KB |
Output isn't correct |
| 9 |
Incorrect |
17 ms |
3364 KB |
Output isn't correct |
| 10 |
Incorrect |
43 ms |
5356 KB |
Output isn't correct |
| 11 |
Incorrect |
222 ms |
13404 KB |
Output isn't correct |
| 12 |
Incorrect |
181 ms |
13572 KB |
Output isn't correct |
| 13 |
Incorrect |
201 ms |
13284 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
7080 KB |
Output is correct |
| 2 |
Incorrect |
294 ms |
21784 KB |
Output isn't correct |
| 3 |
Incorrect |
193 ms |
18748 KB |
Output isn't correct |
| 4 |
Incorrect |
168 ms |
8848 KB |
Output isn't correct |
| 5 |
Incorrect |
160 ms |
8888 KB |
Output isn't correct |
| 6 |
Incorrect |
163 ms |
8468 KB |
Output isn't correct |
| 7 |
Incorrect |
177 ms |
7672 KB |
Output isn't correct |
| 8 |
Correct |
136 ms |
6976 KB |
Output is correct |
| 9 |
Incorrect |
261 ms |
22000 KB |
Output isn't correct |
| 10 |
Incorrect |
295 ms |
21736 KB |
Output isn't correct |
| 11 |
Incorrect |
268 ms |
21820 KB |
Output isn't correct |
| 12 |
Incorrect |
278 ms |
20088 KB |
Output isn't correct |
| 13 |
Correct |
214 ms |
22408 KB |
Output is correct |
| 14 |
Incorrect |
196 ms |
18748 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
12452 KB |
Output isn't correct |
| 2 |
Incorrect |
318 ms |
20580 KB |
Output isn't correct |
| 3 |
Correct |
185 ms |
20832 KB |
Output is correct |
| 4 |
Incorrect |
175 ms |
18248 KB |
Output isn't correct |
| 5 |
Incorrect |
183 ms |
17956 KB |
Output isn't correct |
| 6 |
Incorrect |
203 ms |
18056 KB |
Output isn't correct |
| 7 |
Incorrect |
190 ms |
16920 KB |
Output isn't correct |
| 8 |
Correct |
186 ms |
20760 KB |
Output is correct |
| 9 |
Incorrect |
321 ms |
22236 KB |
Output isn't correct |
| 10 |
Incorrect |
297 ms |
21732 KB |
Output isn't correct |
| 11 |
Incorrect |
304 ms |
21800 KB |
Output isn't correct |
| 12 |
Incorrect |
307 ms |
20764 KB |
Output isn't correct |
| 13 |
Correct |
294 ms |
25488 KB |
Output is correct |
| 14 |
Incorrect |
251 ms |
18620 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
279 ms |
22196 KB |
Output isn't correct |
| 2 |
Incorrect |
298 ms |
20564 KB |
Output isn't correct |
| 3 |
Correct |
234 ms |
24920 KB |
Output is correct |
| 4 |
Incorrect |
285 ms |
22192 KB |
Output isn't correct |
| 5 |
Incorrect |
298 ms |
21956 KB |
Output isn't correct |
| 6 |
Incorrect |
252 ms |
21688 KB |
Output isn't correct |
| 7 |
Incorrect |
299 ms |
20576 KB |
Output isn't correct |
| 8 |
Correct |
263 ms |
25064 KB |
Output is correct |
| 9 |
Incorrect |
219 ms |
18636 KB |
Output isn't correct |
