#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()
{
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];
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 |
Incorrect |
22 ms |
23936 KB |
Output isn't correct |
2 |
Execution timed out |
1054 ms |
33728 KB |
Time limit exceeded |
3 |
Incorrect |
292 ms |
34016 KB |
Output isn't correct |
4 |
Execution timed out |
1068 ms |
23800 KB |
Time limit exceeded |
5 |
Incorrect |
22 ms |
23936 KB |
Output isn't correct |
6 |
Incorrect |
25 ms |
23936 KB |
Output isn't correct |
7 |
Execution timed out |
1077 ms |
24064 KB |
Time limit exceeded |
8 |
Execution timed out |
1040 ms |
23928 KB |
Time limit exceeded |
9 |
Incorrect |
46 ms |
24448 KB |
Output isn't correct |
10 |
Execution timed out |
1081 ms |
26308 KB |
Time limit exceeded |
11 |
Incorrect |
350 ms |
33892 KB |
Output isn't correct |
12 |
Incorrect |
231 ms |
34084 KB |
Output isn't correct |
13 |
Incorrect |
270 ms |
33980 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
164 ms |
27640 KB |
Output is correct |
2 |
Incorrect |
407 ms |
41268 KB |
Output isn't correct |
3 |
Incorrect |
268 ms |
38976 KB |
Output isn't correct |
4 |
Execution timed out |
1066 ms |
29176 KB |
Time limit exceeded |
5 |
Execution timed out |
1075 ms |
28920 KB |
Time limit exceeded |
6 |
Incorrect |
207 ms |
29176 KB |
Output isn't correct |
7 |
Incorrect |
236 ms |
28536 KB |
Output isn't correct |
8 |
Correct |
172 ms |
27864 KB |
Output is correct |
9 |
Incorrect |
363 ms |
41436 KB |
Output isn't correct |
10 |
Incorrect |
442 ms |
41228 KB |
Output isn't correct |
11 |
Incorrect |
364 ms |
41028 KB |
Output isn't correct |
12 |
Incorrect |
393 ms |
39996 KB |
Output isn't correct |
13 |
Correct |
342 ms |
41620 KB |
Output is correct |
14 |
Incorrect |
260 ms |
39028 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
179 ms |
32636 KB |
Output isn't correct |
2 |
Incorrect |
427 ms |
40472 KB |
Output isn't correct |
3 |
Correct |
260 ms |
39928 KB |
Output is correct |
4 |
Incorrect |
268 ms |
38024 KB |
Output isn't correct |
5 |
Incorrect |
279 ms |
37564 KB |
Output isn't correct |
6 |
Incorrect |
280 ms |
37600 KB |
Output isn't correct |
7 |
Incorrect |
262 ms |
36984 KB |
Output isn't correct |
8 |
Correct |
271 ms |
40016 KB |
Output is correct |
9 |
Incorrect |
415 ms |
41592 KB |
Output isn't correct |
10 |
Incorrect |
462 ms |
41164 KB |
Output isn't correct |
11 |
Incorrect |
493 ms |
41200 KB |
Output isn't correct |
12 |
Incorrect |
479 ms |
40312 KB |
Output isn't correct |
13 |
Correct |
421 ms |
44152 KB |
Output is correct |
14 |
Incorrect |
421 ms |
38900 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
442 ms |
41620 KB |
Output isn't correct |
2 |
Incorrect |
434 ms |
40476 KB |
Output isn't correct |
3 |
Correct |
323 ms |
43884 KB |
Output is correct |
4 |
Incorrect |
387 ms |
41592 KB |
Output isn't correct |
5 |
Incorrect |
368 ms |
41080 KB |
Output isn't correct |
6 |
Incorrect |
312 ms |
41080 KB |
Output isn't correct |
7 |
Incorrect |
378 ms |
40312 KB |
Output isn't correct |
8 |
Correct |
289 ms |
43896 KB |
Output is correct |
9 |
Incorrect |
250 ms |
39152 KB |
Output isn't correct |