#include <bits/stdc++.h>
using namespace std;
int n,minn[100005],root,q,sprs[100005][30],cnt[100005],pro[100005],cur;
vector <int> v[100005];
set <pair<int,int > > s;
bool yes[100005];
void dfs (int x,int p)
{
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);
minn[x]=min(minn[x],minn[v[x][i]]);
cnt[x]++;
}
}
}
void build (int x,int p)
{
set <pair<int,int> > s1;
for (int i=0;i<v[x].size();i++)
{
if (v[x][i]!=p)
{
s1.insert({minn[v[x][i]],v[x][i]});
}
}
while (!s1.empty())
{
build(s1.begin()->second,x);
s1.erase(s1.begin());
}
pro[x]=++cur;
}
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({pro[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)
{
cnt[sprs[x][0]]--;
if (!cnt[sprs[x][0]])
s.insert({pro[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({pro[k],k});
if (k!=root)
{
s.erase({pro[sprs[k][0]],sprs[k][0]});
cnt[sprs[k][0]]++;
}
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[x].size();i++)
^
ballmachine.cpp: In function 'void build(int, int)':
ballmachine.cpp:27: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:83: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 |
2680 KB |
Output isn't correct |
| 2 |
Incorrect |
403 ms |
14940 KB |
Output isn't correct |
| 3 |
Incorrect |
264 ms |
15144 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
15144 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
15144 KB |
Output isn't correct |
| 6 |
Incorrect |
5 ms |
15144 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
15144 KB |
Output isn't correct |
| 8 |
Incorrect |
6 ms |
15144 KB |
Output isn't correct |
| 9 |
Incorrect |
26 ms |
15144 KB |
Output isn't correct |
| 10 |
Incorrect |
76 ms |
15144 KB |
Output isn't correct |
| 11 |
Incorrect |
378 ms |
15144 KB |
Output isn't correct |
| 12 |
Incorrect |
265 ms |
15260 KB |
Output isn't correct |
| 13 |
Incorrect |
360 ms |
15260 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
15260 KB |
Output is correct |
| 2 |
Incorrect |
439 ms |
23932 KB |
Output isn't correct |
| 3 |
Correct |
303 ms |
23932 KB |
Output is correct |
| 4 |
Incorrect |
240 ms |
23932 KB |
Output isn't correct |
| 5 |
Incorrect |
244 ms |
23932 KB |
Output isn't correct |
| 6 |
Incorrect |
223 ms |
23932 KB |
Output isn't correct |
| 7 |
Incorrect |
230 ms |
23932 KB |
Output isn't correct |
| 8 |
Correct |
172 ms |
23932 KB |
Output is correct |
| 9 |
Incorrect |
386 ms |
23932 KB |
Output isn't correct |
| 10 |
Incorrect |
420 ms |
23932 KB |
Output isn't correct |
| 11 |
Incorrect |
381 ms |
23932 KB |
Output isn't correct |
| 12 |
Incorrect |
416 ms |
23932 KB |
Output isn't correct |
| 13 |
Correct |
319 ms |
23932 KB |
Output is correct |
| 14 |
Correct |
294 ms |
23932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
207 ms |
23932 KB |
Output isn't correct |
| 2 |
Incorrect |
468 ms |
23932 KB |
Output isn't correct |
| 3 |
Correct |
290 ms |
23932 KB |
Output is correct |
| 4 |
Incorrect |
294 ms |
23932 KB |
Output isn't correct |
| 5 |
Incorrect |
303 ms |
23932 KB |
Output isn't correct |
| 6 |
Incorrect |
292 ms |
23932 KB |
Output isn't correct |
| 7 |
Incorrect |
311 ms |
23932 KB |
Output isn't correct |
| 8 |
Correct |
308 ms |
23932 KB |
Output is correct |
| 9 |
Incorrect |
505 ms |
23932 KB |
Output isn't correct |
| 10 |
Incorrect |
537 ms |
24080 KB |
Output isn't correct |
| 11 |
Incorrect |
539 ms |
24172 KB |
Output isn't correct |
| 12 |
Incorrect |
488 ms |
24172 KB |
Output isn't correct |
| 13 |
Correct |
477 ms |
25584 KB |
Output is correct |
| 14 |
Incorrect |
494 ms |
25584 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
488 ms |
25584 KB |
Output isn't correct |
| 2 |
Incorrect |
487 ms |
25584 KB |
Output isn't correct |
| 3 |
Correct |
354 ms |
25584 KB |
Output is correct |
| 4 |
Incorrect |
443 ms |
25584 KB |
Output isn't correct |
| 5 |
Incorrect |
477 ms |
25584 KB |
Output isn't correct |
| 6 |
Incorrect |
414 ms |
25584 KB |
Output isn't correct |
| 7 |
Incorrect |
468 ms |
25584 KB |
Output isn't correct |
| 8 |
Correct |
370 ms |
25584 KB |
Output is correct |
| 9 |
Correct |
311 ms |
25584 KB |
Output is correct |
