#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std ;
const int N=1e5;
const int M=16;
vector<int>v[N+5];
int dis[N+5], parent[N+5][M+5];
int order[N+5], submin[N+5];
bool is[N+5];
int cnt=0;
bool comp(int a , int b)
{
return submin[a]<submin[b];
}
void dfs1(int c , int p , int d)
{
submin[c]=c;
parent[c][0]=p;
dis[c]=d;
for (int i=1;i<=M;i++)
{
parent[c][i]=parent[parent[c][i-1]][i-1];
}
for (int i=0;i<v[c].size();i++)
{
if(v[c][i]!=p)
{
dfs1(v[c][i],c,d+1);
submin[c]=min(submin[c],submin[v[c][i]]);
}
}
}
void arrange(int c , int p)
{
for (int i=0;i<v[c].size();i++)
{
if(v[c][i]!=p)
{
arrange(v[c][i],c);
}
}
order[c]=cnt++;
}
int findk(int node)
{
for (int i=M;i>=0;i--)
{
if(is[parent[node][i]])
{
node=parent[node][i];
}
}
return node;
}
int main ()
{
int n , q ;
cin >> n >> q ;
int root=1;
for (int i=1;i<=n;i++)
{
int a;
cin >> a ;
if(a)
{
v[a].pb(i);
v[i].pb(a);
}
else
root=i;
}
dfs1(root,root,1);
for (int i=1;i<=n;i++)
sort(v[i].begin(),v[i].end(),comp);
arrange(root,root);
set<pair<int,int>>s;
for (int i=1;i<=n;i++)
{
s.insert({order[i],i});
}
while(q--)
{
int t , k ;
cin >> t >> k ;
if(t==1)
{
if(k)
{
int ans=0;
while(k--)
{
pair<int,int>temp=*(s.begin());
s.erase(temp);
is[temp.ss]=true;
ans=temp.ss;
}
cout<<ans<<"\n";
}
}
else
{
// find the highest ancestor from k
int node=findk(k);
cout<<dis[k]-dis[node]<<"\n";
is[node]=false;
s.insert({order[node],node});
}
}
}
Compilation message
ballmachine.cpp: In function 'void dfs1(int, int, int)':
ballmachine.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (int i=0;i<v[c].size();i++)
| ~^~~~~~~~~~~~
ballmachine.cpp: In function 'void arrange(int, int)':
ballmachine.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i=0;i<v[c].size();i++)
| ~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2636 KB |
Output is correct |
2 |
Correct |
301 ms |
15452 KB |
Output is correct |
3 |
Correct |
242 ms |
15172 KB |
Output is correct |
4 |
Correct |
2 ms |
2648 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
3 ms |
2764 KB |
Output is correct |
7 |
Correct |
5 ms |
2776 KB |
Output is correct |
8 |
Correct |
5 ms |
2764 KB |
Output is correct |
9 |
Correct |
19 ms |
3424 KB |
Output is correct |
10 |
Correct |
55 ms |
5732 KB |
Output is correct |
11 |
Correct |
346 ms |
15320 KB |
Output is correct |
12 |
Correct |
257 ms |
15196 KB |
Output is correct |
13 |
Correct |
280 ms |
15264 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
161 ms |
8016 KB |
Output is correct |
2 |
Correct |
362 ms |
25572 KB |
Output is correct |
3 |
Correct |
250 ms |
21184 KB |
Output is correct |
4 |
Correct |
198 ms |
9924 KB |
Output is correct |
5 |
Correct |
229 ms |
9856 KB |
Output is correct |
6 |
Correct |
183 ms |
9908 KB |
Output is correct |
7 |
Correct |
200 ms |
8844 KB |
Output is correct |
8 |
Correct |
164 ms |
8116 KB |
Output is correct |
9 |
Correct |
336 ms |
25392 KB |
Output is correct |
10 |
Correct |
388 ms |
25508 KB |
Output is correct |
11 |
Correct |
332 ms |
25392 KB |
Output is correct |
12 |
Correct |
408 ms |
23064 KB |
Output is correct |
13 |
Correct |
306 ms |
26152 KB |
Output is correct |
14 |
Correct |
271 ms |
21224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
170 ms |
14020 KB |
Output is correct |
2 |
Correct |
448 ms |
23500 KB |
Output is correct |
3 |
Correct |
262 ms |
24000 KB |
Output is correct |
4 |
Correct |
280 ms |
20776 KB |
Output is correct |
5 |
Correct |
267 ms |
20768 KB |
Output is correct |
6 |
Correct |
275 ms |
20768 KB |
Output is correct |
7 |
Correct |
267 ms |
19108 KB |
Output is correct |
8 |
Correct |
280 ms |
23964 KB |
Output is correct |
9 |
Correct |
503 ms |
25556 KB |
Output is correct |
10 |
Correct |
378 ms |
25548 KB |
Output is correct |
11 |
Correct |
385 ms |
25608 KB |
Output is correct |
12 |
Correct |
370 ms |
23608 KB |
Output is correct |
13 |
Correct |
408 ms |
29656 KB |
Output is correct |
14 |
Correct |
308 ms |
21652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
408 ms |
25716 KB |
Output is correct |
2 |
Correct |
398 ms |
23584 KB |
Output is correct |
3 |
Correct |
308 ms |
29124 KB |
Output is correct |
4 |
Correct |
372 ms |
25668 KB |
Output is correct |
5 |
Correct |
410 ms |
25624 KB |
Output is correct |
6 |
Correct |
349 ms |
25432 KB |
Output is correct |
7 |
Correct |
386 ms |
23608 KB |
Output is correct |
8 |
Correct |
294 ms |
29144 KB |
Output is correct |
9 |
Correct |
253 ms |
21228 KB |
Output is correct |