#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
int n,q;
int par[100007],mi[100007],root,num[100007],cnt=0;
int op,x;
int p[20][100007];
bool stat[100007];
vector <int> edge[100007],edge2[100007];
priority_queue < pair<int,int> , vector < pair<int,int> > , greater < pair<int,int> > > pr;
void read(int &k){
int x;
scanf("%d",&x);
k=x;
}
void print(int x){
printf("%d\n",x);
}
void dfs(int u){
vector < pair<int,int> > cur;
mi[u]=u;
for(int i=0;i<(int)edge[u].size();i++){
int v=edge[u][i];
if(v==par[u]) continue;
dfs(v);
mi[u]=min(mi[u],mi[v]);
cur.pb(mp(mi[v],v));
}
sort(cur.begin(),cur.end());
for(int i=0;i<(int)cur.size();i++){
edge2[u].pb(cur[i].se);
}
}
void dfs2(int u){
for(int i=0;i<(int)edge2[u].size();i++){
int v=edge2[u][i];
if(v==par[u]) continue;
dfs2(v);
}
cnt++;
num[u]=cnt;
}
int main(){
read(n);
read(q);
for(int i=1;i<=n;i++){
read(par[i]);
edge[par[i]].pb(i);
p[0][i]=par[i];
if(par[i]==0) root=i;
mi[i]=1e9;
}
dfs(root);
dfs2(root);
for(int i=1;i<=n;i++) pr.push(mp(num[i],i));
for(int i=1;i<=19;i++){
for(int j=1;j<=n;j++){
p[i][j]=p[i-1][p[i-1][j]];
}
}
while(q--){
read(op);
read(x);
if(op==1){
int ans=0;
while(x>0){
x--;
int u=pr.top().se;
stat[u]=true;
ans=u;
pr.pop();
}
print(ans);
}
else{
int ans=0;
for(int i=19;i>=0;i--){
int pr=p[i][x];
if(stat[pr]){
x=pr;
ans+=(1<<i);
}
}
stat[x]=false;
print(ans);
}
}
}
Compilation message
ballmachine.cpp: In function 'void read(int&)':
ballmachine.cpp:16:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
15788 KB |
Output isn't correct |
| 2 |
Incorrect |
166 ms |
18688 KB |
Output isn't correct |
| 3 |
Incorrect |
119 ms |
18688 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
15788 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
15788 KB |
Output isn't correct |
| 6 |
Correct |
0 ms |
15788 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
15788 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
15788 KB |
Output isn't correct |
| 9 |
Incorrect |
9 ms |
16056 KB |
Output isn't correct |
| 10 |
Incorrect |
19 ms |
16504 KB |
Output isn't correct |
| 11 |
Incorrect |
146 ms |
18688 KB |
Output isn't correct |
| 12 |
Incorrect |
103 ms |
18688 KB |
Output isn't correct |
| 13 |
Incorrect |
123 ms |
18688 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
19264 KB |
Output isn't correct |
| 2 |
Incorrect |
233 ms |
26656 KB |
Output isn't correct |
| 3 |
Incorrect |
109 ms |
20512 KB |
Output isn't correct |
| 4 |
Incorrect |
93 ms |
19196 KB |
Output isn't correct |
| 5 |
Incorrect |
66 ms |
18932 KB |
Output isn't correct |
| 6 |
Incorrect |
49 ms |
18936 KB |
Output isn't correct |
| 7 |
Incorrect |
66 ms |
17976 KB |
Output isn't correct |
| 8 |
Incorrect |
56 ms |
19264 KB |
Output isn't correct |
| 9 |
Incorrect |
209 ms |
27496 KB |
Output isn't correct |
| 10 |
Incorrect |
216 ms |
26656 KB |
Output isn't correct |
| 11 |
Incorrect |
189 ms |
26656 KB |
Output isn't correct |
| 12 |
Incorrect |
206 ms |
23780 KB |
Output isn't correct |
| 13 |
Incorrect |
136 ms |
32452 KB |
Output isn't correct |
| 14 |
Incorrect |
129 ms |
20512 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
21616 KB |
Output is correct |
| 2 |
Correct |
246 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
176 ms |
31036 KB |
Output is correct |
| 4 |
Correct |
169 ms |
25460 KB |
Output is correct |
| 5 |
Correct |
146 ms |
24788 KB |
Output is correct |
| 6 |
Correct |
163 ms |
24796 KB |
Output is correct |
| 7 |
Correct |
133 ms |
22608 KB |
Output is correct |
| 8 |
Correct |
179 ms |
31032 KB |
Output is correct |
| 9 |
Correct |
243 ms |
27496 KB |
Output is correct |
| 10 |
Correct |
249 ms |
26672 KB |
Output is correct |
| 11 |
Correct |
263 ms |
26668 KB |
Output is correct |
| 12 |
Correct |
253 ms |
23928 KB |
Output is correct |
| 13 |
Correct |
269 ms |
34476 KB |
Output is correct |
| 14 |
Correct |
179 ms |
20520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
263 ms |
27496 KB |
Output isn't correct |
| 2 |
Incorrect |
219 ms |
23932 KB |
Output isn't correct |
| 3 |
Incorrect |
179 ms |
34476 KB |
Output isn't correct |
| 4 |
Incorrect |
253 ms |
27492 KB |
Output isn't correct |
| 5 |
Incorrect |
249 ms |
26672 KB |
Output isn't correct |
| 6 |
Incorrect |
206 ms |
26676 KB |
Output isn't correct |
| 7 |
Incorrect |
223 ms |
23928 KB |
Output isn't correct |
| 8 |
Incorrect |
189 ms |
34472 KB |
Output isn't correct |
| 9 |
Incorrect |
109 ms |
20520 KB |
Output isn't correct |
