#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())
{
Nr[p]--;
S.erase({Val[p],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 |
Incorrect |
6 ms |
2688 KB |
Output isn't correct |
2 |
Execution timed out |
1091 ms |
11552 KB |
Time limit exceeded |
3 |
Incorrect |
69 ms |
11640 KB |
Output isn't correct |
4 |
Execution timed out |
1092 ms |
2816 KB |
Time limit exceeded |
5 |
Incorrect |
6 ms |
2816 KB |
Output isn't correct |
6 |
Incorrect |
7 ms |
2944 KB |
Output isn't correct |
7 |
Execution timed out |
1095 ms |
2944 KB |
Time limit exceeded |
8 |
Execution timed out |
1090 ms |
2944 KB |
Time limit exceeded |
9 |
Execution timed out |
1095 ms |
3328 KB |
Time limit exceeded |
10 |
Execution timed out |
1093 ms |
4992 KB |
Time limit exceeded |
11 |
Incorrect |
142 ms |
12060 KB |
Output isn't correct |
12 |
Incorrect |
67 ms |
11640 KB |
Output isn't correct |
13 |
Incorrect |
120 ms |
11640 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
6008 KB |
Output is correct |
2 |
Incorrect |
195 ms |
17256 KB |
Output isn't correct |
3 |
Correct |
91 ms |
15220 KB |
Output is correct |
4 |
Execution timed out |
1091 ms |
7672 KB |
Time limit exceeded |
5 |
Incorrect |
80 ms |
7928 KB |
Output isn't correct |
6 |
Incorrect |
73 ms |
7672 KB |
Output isn't correct |
7 |
Incorrect |
83 ms |
7160 KB |
Output isn't correct |
8 |
Correct |
35 ms |
6008 KB |
Output is correct |
9 |
Incorrect |
172 ms |
17720 KB |
Output isn't correct |
10 |
Incorrect |
171 ms |
17144 KB |
Output isn't correct |
11 |
Incorrect |
149 ms |
17144 KB |
Output isn't correct |
12 |
Incorrect |
181 ms |
16248 KB |
Output isn't correct |
13 |
Correct |
74 ms |
15992 KB |
Output is correct |
14 |
Correct |
86 ms |
15220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
98 ms |
9976 KB |
Output isn't correct |
2 |
Incorrect |
218 ms |
16376 KB |
Output isn't correct |
3 |
Correct |
122 ms |
15144 KB |
Output is correct |
4 |
Incorrect |
110 ms |
14200 KB |
Output isn't correct |
5 |
Incorrect |
114 ms |
14200 KB |
Output isn't correct |
6 |
Incorrect |
113 ms |
14072 KB |
Output isn't correct |
7 |
Incorrect |
109 ms |
13560 KB |
Output isn't correct |
8 |
Correct |
99 ms |
15100 KB |
Output is correct |
9 |
Incorrect |
202 ms |
17016 KB |
Output isn't correct |
10 |
Incorrect |
183 ms |
17272 KB |
Output isn't correct |
11 |
Incorrect |
186 ms |
17276 KB |
Output isn't correct |
12 |
Incorrect |
193 ms |
16460 KB |
Output isn't correct |
13 |
Correct |
186 ms |
18424 KB |
Output is correct |
14 |
Incorrect |
175 ms |
16244 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
172 ms |
17144 KB |
Output isn't correct |
2 |
Incorrect |
178 ms |
16376 KB |
Output isn't correct |
3 |
Correct |
81 ms |
17528 KB |
Output is correct |
4 |
Incorrect |
182 ms |
17144 KB |
Output isn't correct |
5 |
Incorrect |
169 ms |
17144 KB |
Output isn't correct |
6 |
Incorrect |
148 ms |
17144 KB |
Output isn't correct |
7 |
Incorrect |
179 ms |
16352 KB |
Output isn't correct |
8 |
Correct |
76 ms |
17528 KB |
Output is correct |
9 |
Correct |
81 ms |
15220 KB |
Output is correct |