#include<bits/stdc++.h>
using namespace std;
int pa[100005][18];
vector<int> g[100005];
int mn[100005];
int tout[100005],ord[100005],counter=0;
set<int> s;
void dfs1(int u){
mn[u]=u;
for(auto v:g[u]){
dfs1(v);
mn[u]=min(mn[u],mn[v]);
}
}
void dfs2(int u){
for(auto v:g[u])
dfs2(v);
tout[u]=++counter;
ord[counter]=u;
}
main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,q;
cin >> n >> q;
int rt=0;
for(int i=1,x;i<=n;i++){
cin >> x;
pa[i][0]=x;
if(!x)
rt=i;
else
g[x].push_back(i);
}
dfs1(rt);
for(int i=1;i<=n;i++){
sort(g[i].begin(),g[i].end(),[&](int x,int y){
return mn[x]<mn[y];
});
}
for(int j=1;j<18;j++)
for(int i=1;i<=n;i++)
pa[i][j]=pa[pa[i][j-1]][j-1];
dfs2(rt);
for(int i=1;i<=n;i++)
s.insert(i);
int t,x,ans;
while(q--){
cin >> t >> x;
if(t==1){
ans=0;
while(x--){
ans=*s.begin();
s.erase(s.begin());
}
cout << ord[ans] << "\n";
}
else{
ans=0;
for(int i=17;i>=0;i--){
int px=pa[x][i];
if(px!=0&&s.find(tout[px])==s.end()){
ans+=(1<<i);
x=px;
}
}
s.insert(tout[x]);
cout << ans << "\n";
}
}
}
Compilation message
ballmachine.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
26 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
124 ms |
13428 KB |
Output is correct |
3 |
Correct |
60 ms |
13428 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2680 KB |
Output is correct |
6 |
Correct |
3 ms |
2772 KB |
Output is correct |
7 |
Correct |
2 ms |
2772 KB |
Output is correct |
8 |
Correct |
3 ms |
2772 KB |
Output is correct |
9 |
Correct |
8 ms |
3332 KB |
Output is correct |
10 |
Correct |
24 ms |
5316 KB |
Output is correct |
11 |
Correct |
128 ms |
13456 KB |
Output is correct |
12 |
Correct |
68 ms |
13516 KB |
Output is correct |
13 |
Correct |
96 ms |
13460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
7244 KB |
Output is correct |
2 |
Correct |
347 ms |
21384 KB |
Output is correct |
3 |
Correct |
84 ms |
18032 KB |
Output is correct |
4 |
Correct |
94 ms |
8848 KB |
Output is correct |
5 |
Correct |
187 ms |
8724 KB |
Output is correct |
6 |
Correct |
132 ms |
8652 KB |
Output is correct |
7 |
Correct |
125 ms |
7952 KB |
Output is correct |
8 |
Correct |
48 ms |
7172 KB |
Output is correct |
9 |
Correct |
231 ms |
21816 KB |
Output is correct |
10 |
Correct |
281 ms |
21392 KB |
Output is correct |
11 |
Correct |
282 ms |
21448 KB |
Output is correct |
12 |
Correct |
253 ms |
19836 KB |
Output is correct |
13 |
Correct |
135 ms |
22392 KB |
Output is correct |
14 |
Correct |
104 ms |
17992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
12268 KB |
Output is correct |
2 |
Correct |
324 ms |
20340 KB |
Output is correct |
3 |
Correct |
199 ms |
20472 KB |
Output is correct |
4 |
Correct |
137 ms |
18068 KB |
Output is correct |
5 |
Correct |
189 ms |
17576 KB |
Output is correct |
6 |
Correct |
172 ms |
17468 KB |
Output is correct |
7 |
Correct |
184 ms |
16740 KB |
Output is correct |
8 |
Correct |
203 ms |
20452 KB |
Output is correct |
9 |
Correct |
221 ms |
21964 KB |
Output is correct |
10 |
Correct |
313 ms |
21556 KB |
Output is correct |
11 |
Correct |
314 ms |
21588 KB |
Output is correct |
12 |
Correct |
343 ms |
20440 KB |
Output is correct |
13 |
Correct |
360 ms |
25220 KB |
Output is correct |
14 |
Correct |
142 ms |
18508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
255 ms |
22104 KB |
Output is correct |
2 |
Correct |
297 ms |
20364 KB |
Output is correct |
3 |
Correct |
147 ms |
24944 KB |
Output is correct |
4 |
Correct |
246 ms |
22140 KB |
Output is correct |
5 |
Correct |
328 ms |
21580 KB |
Output is correct |
6 |
Correct |
317 ms |
21516 KB |
Output is correct |
7 |
Correct |
304 ms |
20356 KB |
Output is correct |
8 |
Correct |
159 ms |
24900 KB |
Output is correct |
9 |
Correct |
91 ms |
18040 KB |
Output is correct |