#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
int P[20][100005];
vector<int> Sons[100005];
int Val[100005],Nr[100005];
bool Ball[100005];
set<pair<int,int> > S;
void dfs(int nod)
{
Val[nod]=nod;
for(auto son:Sons[nod])
{
dfs(son);
Val[nod]=min(Val[nod],Val[nod]);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,q;
cin>>n>>q;
int root=0;
for(int i=1; i<=n; i++)
{
cin>>P[0][i];
Sons[P[0][i]].push_back(i);
if(P[0][i]==0)
root=i;
}
for(int i=1; i<=16; i++)
{
for(int j=1; j<=n; j++)
P[i][j]=P[i-1][P[i-1][j]];
}
dfs(root);
for(int i=1; i<=n; i++)
{
if(Sons[i].size()==0)
S.insert({Val[i],i});
}
for(int i=1; i<=q; i++)
{
int tip,x;
cin>>tip>>x;
if(tip==1)
{
int rez=0;
for(int j=1; j<=x; j++) //suma x-ilor va fi max n+q
{
int nod=(*S.begin()).second;
S.erase(S.begin());
Ball[nod]=1;
rez=nod;
if(nod!=root)
{
int p=P[0][nod];
Nr[p]++;
if(Nr[p]==Sons[p].size())
S.insert({Val[p],p});
}
}
cout<<rez<<"\n";
}
else
{
int rez=0;
for(int i=16; i>=0; i--)
{
if(Ball[P[i][x]])
{
rez+=(1<<i);
x=P[i][x];
}
}
cout<<rez<<"\n";
Ball[x]=0;
if(x!=root)
{
int p=P[0][x];
if(Nr[p]==Sons[p].size())
S.erase({Val[p],p});
Nr[p]--;
}
S.insert({Val[x],x});
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:76:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(Nr[p]==Sons[p].size())
~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:101:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(Nr[p]==Sons[p].size())
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1096 ms |
2816 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1090 ms |
10488 KB |
Time limit exceeded |
| 3 |
Incorrect |
63 ms |
10720 KB |
Output isn't correct |
| 4 |
Execution timed out |
1098 ms |
2816 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1088 ms |
2816 KB |
Time limit exceeded |
| 6 |
Incorrect |
7 ms |
2944 KB |
Output isn't correct |
| 7 |
Execution timed out |
1093 ms |
2944 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1095 ms |
2944 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1084 ms |
3200 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1097 ms |
4736 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1094 ms |
10488 KB |
Time limit exceeded |
| 12 |
Incorrect |
61 ms |
10616 KB |
Output isn't correct |
| 13 |
Incorrect |
107 ms |
10532 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
5496 KB |
Output is correct |
| 2 |
Execution timed out |
1091 ms |
15480 KB |
Time limit exceeded |
| 3 |
Correct |
68 ms |
14324 KB |
Output is correct |
| 4 |
Execution timed out |
1093 ms |
6904 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1095 ms |
6656 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1087 ms |
6776 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1097 ms |
6144 KB |
Time limit exceeded |
| 8 |
Correct |
34 ms |
5504 KB |
Output is correct |
| 9 |
Execution timed out |
1090 ms |
16252 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1095 ms |
15480 KB |
Time limit exceeded |
| 11 |
Incorrect |
131 ms |
15864 KB |
Output isn't correct |
| 12 |
Incorrect |
176 ms |
15000 KB |
Output isn't correct |
| 13 |
Correct |
74 ms |
14968 KB |
Output is correct |
| 14 |
Correct |
75 ms |
14068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
9336 KB |
Output isn't correct |
| 2 |
Incorrect |
187 ms |
15096 KB |
Output isn't correct |
| 3 |
Correct |
161 ms |
14200 KB |
Output is correct |
| 4 |
Incorrect |
119 ms |
13304 KB |
Output isn't correct |
| 5 |
Incorrect |
113 ms |
13304 KB |
Output isn't correct |
| 6 |
Incorrect |
111 ms |
13176 KB |
Output isn't correct |
| 7 |
Incorrect |
111 ms |
12540 KB |
Output isn't correct |
| 8 |
Correct |
113 ms |
14072 KB |
Output is correct |
| 9 |
Incorrect |
197 ms |
15736 KB |
Output isn't correct |
| 10 |
Incorrect |
184 ms |
15864 KB |
Output isn't correct |
| 11 |
Incorrect |
201 ms |
15992 KB |
Output isn't correct |
| 12 |
Incorrect |
181 ms |
15096 KB |
Output isn't correct |
| 13 |
Correct |
171 ms |
17016 KB |
Output is correct |
| 14 |
Incorrect |
180 ms |
14708 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1096 ms |
15352 KB |
Time limit exceeded |
| 2 |
Incorrect |
170 ms |
14968 KB |
Output isn't correct |
| 3 |
Correct |
75 ms |
16380 KB |
Output is correct |
| 4 |
Execution timed out |
1088 ms |
15352 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1091 ms |
15608 KB |
Time limit exceeded |
| 6 |
Incorrect |
126 ms |
15736 KB |
Output isn't correct |
| 7 |
Incorrect |
167 ms |
15096 KB |
Output isn't correct |
| 8 |
Correct |
82 ms |
16504 KB |
Output is correct |
| 9 |
Correct |
81 ms |
14196 KB |
Output is correct |
