#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[son]);
}
}
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 |
1091 ms |
2816 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1095 ms |
10616 KB |
Time limit exceeded |
| 3 |
Incorrect |
66 ms |
11000 KB |
Output isn't correct |
| 4 |
Execution timed out |
1096 ms |
2816 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1090 ms |
2816 KB |
Time limit exceeded |
| 6 |
Incorrect |
6 ms |
2944 KB |
Output isn't correct |
| 7 |
Execution timed out |
1093 ms |
2944 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1092 ms |
2944 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1092 ms |
3328 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1092 ms |
4864 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1095 ms |
10360 KB |
Time limit exceeded |
| 12 |
Incorrect |
64 ms |
11256 KB |
Output isn't correct |
| 13 |
Incorrect |
99 ms |
10744 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
6136 KB |
Output is correct |
| 2 |
Execution timed out |
1088 ms |
16252 KB |
Time limit exceeded |
| 3 |
Correct |
71 ms |
14580 KB |
Output is correct |
| 4 |
Execution timed out |
1088 ms |
7152 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1088 ms |
6912 KB |
Time limit exceeded |
| 6 |
Incorrect |
69 ms |
7544 KB |
Output isn't correct |
| 7 |
Execution timed out |
1085 ms |
7012 KB |
Time limit exceeded |
| 8 |
Correct |
35 ms |
6136 KB |
Output is correct |
| 9 |
Incorrect |
153 ms |
17784 KB |
Output isn't correct |
| 10 |
Execution timed out |
1090 ms |
16252 KB |
Time limit exceeded |
| 11 |
Incorrect |
131 ms |
17004 KB |
Output isn't correct |
| 12 |
Incorrect |
159 ms |
15736 KB |
Output isn't correct |
| 13 |
Correct |
93 ms |
16632 KB |
Output is correct |
| 14 |
Correct |
72 ms |
14544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
9976 KB |
Output isn't correct |
| 2 |
Incorrect |
177 ms |
15864 KB |
Output isn't correct |
| 3 |
Correct |
147 ms |
15692 KB |
Output is correct |
| 4 |
Incorrect |
110 ms |
14072 KB |
Output isn't correct |
| 5 |
Incorrect |
113 ms |
14204 KB |
Output isn't correct |
| 6 |
Incorrect |
109 ms |
14200 KB |
Output isn't correct |
| 7 |
Incorrect |
118 ms |
13304 KB |
Output isn't correct |
| 8 |
Correct |
110 ms |
15736 KB |
Output is correct |
| 9 |
Incorrect |
178 ms |
16864 KB |
Output isn't correct |
| 10 |
Incorrect |
183 ms |
17040 KB |
Output isn't correct |
| 11 |
Incorrect |
178 ms |
17120 KB |
Output isn't correct |
| 12 |
Incorrect |
170 ms |
15736 KB |
Output isn't correct |
| 13 |
Correct |
188 ms |
18996 KB |
Output is correct |
| 14 |
Incorrect |
170 ms |
15220 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
16096 KB |
Time limit exceeded |
| 2 |
Incorrect |
190 ms |
15888 KB |
Output isn't correct |
| 3 |
Correct |
90 ms |
18296 KB |
Output is correct |
| 4 |
Execution timed out |
1093 ms |
16120 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1092 ms |
16504 KB |
Time limit exceeded |
| 6 |
Incorrect |
135 ms |
16888 KB |
Output isn't correct |
| 7 |
Incorrect |
228 ms |
15736 KB |
Output isn't correct |
| 8 |
Correct |
83 ms |
18304 KB |
Output is correct |
| 9 |
Correct |
75 ms |
14580 KB |
Output is correct |
