#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1000000];
int mn[1000000];
bool cmp(int a,int b)
{
return mn[a]<mn[b];
}
void pre(int v)
{
mn[v]=v;
for (auto u:adj[v])
{
pre(u);
mn[v]=min(mn[v],mn[u]);
}
}
int pa[1000001][21];
int ord[1000001];
int tt=1;
void dfs(int v)
{
for (auto u:adj[v])
dfs(u);
ord[v]=tt++;
}
bool has[1000000];
int main()
{
//freopen("out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,q;
cin>>n>>q;
int root=-1;
for (int i=1;i<=n;i++)
{
cin>>pa[i][0];
if (pa[i][0]==0) root = i;
else adj[pa[i][0]].push_back(i);
}
for (int j=1;j<=18;j++)
for (int i=1;i<=n;i++)
pa[i][j]=pa[pa[i][j-1]][j-1];
pre(root);
for (int i=1;i<=n;i++)
sort(adj[i].begin(),adj[i].end(),cmp);
dfs(root);
set<pair<int,int> > s;
for (int i=1;i<=n;i++)
s.insert({ord[i],i});
while(q--)
{
int t,v;
cin>>t>>v;
if (t==1)
{
pair<int,int> p;
while(v--)
{
p = *s.begin();
s.erase(s.begin());
has[p.second]=1;
}
cout<<p.second<<endl;
}
else
{
int u = v;
int ret=0;
for (int i=18;i>=0;i--)
if (has[pa[u][i]])
u = pa[u][i] , ret+=(1<<i);
has[u]=0;
s.insert({ord[u],u});
cout<<ret<<endl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23928 KB |
Output is correct |
2 |
Correct |
387 ms |
34188 KB |
Output is correct |
3 |
Correct |
239 ms |
34296 KB |
Output is correct |
4 |
Correct |
23 ms |
23808 KB |
Output is correct |
5 |
Correct |
30 ms |
23936 KB |
Output is correct |
6 |
Correct |
24 ms |
23936 KB |
Output is correct |
7 |
Correct |
26 ms |
24064 KB |
Output is correct |
8 |
Correct |
29 ms |
24056 KB |
Output is correct |
9 |
Correct |
38 ms |
24448 KB |
Output is correct |
10 |
Correct |
86 ms |
26360 KB |
Output is correct |
11 |
Correct |
360 ms |
34176 KB |
Output is correct |
12 |
Correct |
301 ms |
34296 KB |
Output is correct |
13 |
Correct |
355 ms |
34236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
28136 KB |
Output is correct |
2 |
Correct |
448 ms |
42056 KB |
Output is correct |
3 |
Correct |
303 ms |
39028 KB |
Output is correct |
4 |
Correct |
265 ms |
29704 KB |
Output is correct |
5 |
Correct |
228 ms |
29432 KB |
Output is correct |
6 |
Correct |
226 ms |
29432 KB |
Output is correct |
7 |
Correct |
252 ms |
28792 KB |
Output is correct |
8 |
Correct |
168 ms |
28124 KB |
Output is correct |
9 |
Correct |
463 ms |
42872 KB |
Output is correct |
10 |
Correct |
450 ms |
42104 KB |
Output is correct |
11 |
Correct |
445 ms |
42256 KB |
Output is correct |
12 |
Correct |
497 ms |
40572 KB |
Output is correct |
13 |
Correct |
410 ms |
43268 KB |
Output is correct |
14 |
Correct |
306 ms |
39184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
33400 KB |
Output is correct |
2 |
Correct |
554 ms |
41388 KB |
Output is correct |
3 |
Correct |
403 ms |
41592 KB |
Output is correct |
4 |
Correct |
335 ms |
39060 KB |
Output is correct |
5 |
Correct |
411 ms |
38492 KB |
Output is correct |
6 |
Correct |
377 ms |
38692 KB |
Output is correct |
7 |
Correct |
355 ms |
37624 KB |
Output is correct |
8 |
Correct |
398 ms |
41592 KB |
Output is correct |
9 |
Correct |
608 ms |
42748 KB |
Output is correct |
10 |
Correct |
526 ms |
42360 KB |
Output is correct |
11 |
Correct |
543 ms |
42532 KB |
Output is correct |
12 |
Correct |
555 ms |
41212 KB |
Output is correct |
13 |
Correct |
513 ms |
46044 KB |
Output is correct |
14 |
Correct |
474 ms |
39308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
462 ms |
42872 KB |
Output is correct |
2 |
Correct |
478 ms |
41180 KB |
Output is correct |
3 |
Correct |
397 ms |
45820 KB |
Output is correct |
4 |
Correct |
548 ms |
42876 KB |
Output is correct |
5 |
Correct |
526 ms |
42348 KB |
Output is correct |
6 |
Correct |
411 ms |
42232 KB |
Output is correct |
7 |
Correct |
575 ms |
41252 KB |
Output is correct |
8 |
Correct |
391 ms |
45828 KB |
Output is correct |
9 |
Correct |
308 ms |
39148 KB |
Output is correct |