#include <bits/stdc++.h>
using namespace std;
int n,minn[100005],root,sz[100005],q,sprs[100005][30];
vector <int> v[100005];
set <pair<int,int > > s;
bool yes[100005];
void dfs (int x,int p)
{
sz[x]=1;
minn[x]=x;
if (p!=-1)
sprs[x][0]=p;
for (int i=1;i<30;i++)
sprs[x][i]=sprs[sprs[x][i-1]][i-1];
for (int i=0;i<v[x].size();i++)
{
if (v[x][i]!=p)
{
dfs(v[x][i],x);
sz[x]+=sz[v[x][i]];
minn[x]=min(minn[x],minn[v[x][i]]);
}
}
}
int main()
{
cin >>n>>q;
for (int i=1;i<=n;i++)
{
int a;
cin >>a;
if (!a)
root=i;
else
{
v[a].push_back(i);
v[i].push_back(a);
}
}
dfs (root,-1);
for (int i=1;i<=n;i++)
{
if (v[i].size()==1&&i!=root)
{
s.insert({minn[i],i});
}
}
while (q--)
{
int t,k;
cin >>t>>k;
if (t==1)
{
int x;
while (k--&&!s.empty())
{
x= s.begin()->second;
s.erase(s.begin());
yes[x]=true;
if (x!=root)
s.insert({minn[sprs[x][0]],sprs[x][0]});
}
cout <<x<<"\n";
}
else
{
int ans=0;
for (int i=29;i>=0;i--)
{
if (yes[sprs[k][i]])
{
k=sprs[k][i];
ans+= (1<<i);
}
}
cout <<ans<<"\n";
yes[k]=false;
s.insert({minn[k],k});
if (sprs[k][0]!=root)
s.erase({minn[sprs[k][0]],k});
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[x].size();i++)
^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:63:20: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
cout <<x<<"\n";
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2684 KB |
Output isn't correct |
| 2 |
Incorrect |
375 ms |
16120 KB |
Output isn't correct |
| 3 |
Incorrect |
267 ms |
17212 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
17212 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
17212 KB |
Output isn't correct |
| 6 |
Incorrect |
5 ms |
17212 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
17212 KB |
Output isn't correct |
| 8 |
Incorrect |
7 ms |
17212 KB |
Output isn't correct |
| 9 |
Incorrect |
26 ms |
17212 KB |
Output isn't correct |
| 10 |
Incorrect |
72 ms |
17212 KB |
Output isn't correct |
| 11 |
Incorrect |
379 ms |
18808 KB |
Output isn't correct |
| 12 |
Incorrect |
268 ms |
19788 KB |
Output isn't correct |
| 13 |
Incorrect |
366 ms |
20748 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
179 ms |
20748 KB |
Output isn't correct |
| 2 |
Incorrect |
483 ms |
32480 KB |
Output isn't correct |
| 3 |
Incorrect |
304 ms |
32480 KB |
Output isn't correct |
| 4 |
Incorrect |
246 ms |
32480 KB |
Output isn't correct |
| 5 |
Incorrect |
258 ms |
32480 KB |
Output isn't correct |
| 6 |
Incorrect |
249 ms |
32480 KB |
Output isn't correct |
| 7 |
Incorrect |
245 ms |
32480 KB |
Output isn't correct |
| 8 |
Incorrect |
179 ms |
32480 KB |
Output isn't correct |
| 9 |
Incorrect |
397 ms |
37664 KB |
Output isn't correct |
| 10 |
Incorrect |
471 ms |
39788 KB |
Output isn't correct |
| 11 |
Incorrect |
416 ms |
41148 KB |
Output isn't correct |
| 12 |
Incorrect |
445 ms |
41148 KB |
Output isn't correct |
| 13 |
Incorrect |
347 ms |
42948 KB |
Output isn't correct |
| 14 |
Incorrect |
300 ms |
42948 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
42948 KB |
Output isn't correct |
| 2 |
Incorrect |
455 ms |
44744 KB |
Output isn't correct |
| 3 |
Correct |
300 ms |
44760 KB |
Output is correct |
| 4 |
Incorrect |
266 ms |
44760 KB |
Output isn't correct |
| 5 |
Incorrect |
299 ms |
44864 KB |
Output isn't correct |
| 6 |
Incorrect |
306 ms |
45932 KB |
Output isn't correct |
| 7 |
Incorrect |
293 ms |
45932 KB |
Output isn't correct |
| 8 |
Correct |
284 ms |
49460 KB |
Output is correct |
| 9 |
Incorrect |
433 ms |
53032 KB |
Output isn't correct |
| 10 |
Incorrect |
461 ms |
54736 KB |
Output isn't correct |
| 11 |
Incorrect |
496 ms |
56200 KB |
Output isn't correct |
| 12 |
Incorrect |
448 ms |
56200 KB |
Output isn't correct |
| 13 |
Correct |
461 ms |
61256 KB |
Output is correct |
| 14 |
Incorrect |
463 ms |
61256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
470 ms |
61256 KB |
Output isn't correct |
| 2 |
Incorrect |
478 ms |
61256 KB |
Output isn't correct |
| 3 |
Incorrect |
364 ms |
66196 KB |
Output isn't correct |
| 4 |
Incorrect |
456 ms |
66196 KB |
Output isn't correct |
| 5 |
Incorrect |
448 ms |
66860 KB |
Output isn't correct |
| 6 |
Incorrect |
434 ms |
68080 KB |
Output isn't correct |
| 7 |
Incorrect |
475 ms |
68080 KB |
Output isn't correct |
| 8 |
Incorrect |
358 ms |
72768 KB |
Output isn't correct |
| 9 |
Incorrect |
315 ms |
72768 KB |
Output isn't correct |
