#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int n,q;
int root;
const int MAXN = 1e5+5;
const int MAXK = 25;
vector<int> v1[MAXN];
int par[MAXN][25];
int subtreemin[MAXN];
int currtime = 1;
bool occupied[MAXN];
int timer[MAXN];
int depth[MAXN];
bool cmp(int x,int y){
return subtreemin[x]<subtreemin[y];
}
bool cmp2(int x,int y){
return timer[x]<timer[y];
}
set<int,decltype(&cmp2)> s1(&cmp2);
void dfs(int curr){
subtreemin[curr] = curr;
for(int x:v1[curr]){
depth[x] = depth[curr]+1;
dfs(x);
subtreemin[curr] = min(subtreemin[curr],subtreemin[x]);
}
}
void dfs2(int curr){
for(int x:v1[curr]){
dfs2(x);
}
timer[curr] = currtime++;
//cout<<curr<<" "<<timer[curr]<<endl;
s1.insert(curr);
}
int addball(){
int ans = *s1.begin();
s1.erase(s1.begin());
occupied[ans] = true;
return ans;
}
int removeball(int x){
int original = x;
for(int i=19;i>=0;i--){
if(par[x][i]!=-1 && occupied[par[x][i]]){
x=par[x][i];
}
}
occupied[x] = false;
s1.insert(x);
return depth[original]-depth[x];
}
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
int p;
cin>>p;
if(p==0){
root = i;
par[i][0] = -1;
continue;
}
par[i][0] = p;
v1[p].push_back(i);
}
depth[root] = 0;
for(int i=1;i<=n;i++){
subtreemin[i] = MAXN;
}
dfs(root);
for(int i=1;i<=n;i++){
sort(v1[i].begin(),v1[i].end(),cmp);
}
dfs2(root);
for(int i=1;i<=MAXK;i++){
for(int j=1;j<=n;j++){
if(par[i][j-1] == -1){
par[i][j] = -1;
}else{
par[i][j] = par[par[i][j-1]][j-1];
}
}
}
for(int i=1;i<=q;i++){
int t;
cin>>t;
if(t==1){
int val;
cin>>val;
int x;
for(int j=1;j<=val;j++){
x = addball();
// cout<<123<<" "<<x<<endl;
}
cout<<x<<endl;
}else{
int val;
cin>>val;
cout<<removeball(val)<<endl;
}
}
}
Compilation message
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:104:19: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
cout<<x<<endl;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2724 KB |
Output isn't correct |
| 2 |
Incorrect |
564 ms |
15388 KB |
Output isn't correct |
| 3 |
Correct |
455 ms |
15280 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
2680 KB |
Output isn't correct |
| 6 |
Incorrect |
7 ms |
2936 KB |
Output isn't correct |
| 7 |
Execution timed out |
1076 ms |
2808 KB |
Time limit exceeded |
| 8 |
Incorrect |
10 ms |
2908 KB |
Output isn't correct |
| 9 |
Incorrect |
42 ms |
3448 KB |
Output isn't correct |
| 10 |
Incorrect |
118 ms |
5752 KB |
Output isn't correct |
| 11 |
Incorrect |
596 ms |
15460 KB |
Output isn't correct |
| 12 |
Correct |
455 ms |
15340 KB |
Output is correct |
| 13 |
Incorrect |
535 ms |
15564 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
314 ms |
7804 KB |
Output is correct |
| 2 |
Runtime error |
182 ms |
46504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
150 ms |
40308 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Incorrect |
398 ms |
9980 KB |
Output isn't correct |
| 5 |
Incorrect |
398 ms |
9552 KB |
Output isn't correct |
| 6 |
Incorrect |
397 ms |
9792 KB |
Output isn't correct |
| 7 |
Incorrect |
388 ms |
8788 KB |
Output isn't correct |
| 8 |
Correct |
318 ms |
7732 KB |
Output is correct |
| 9 |
Runtime error |
167 ms |
47164 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
166 ms |
46328 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Incorrect |
576 ms |
24228 KB |
Output isn't correct |
| 12 |
Incorrect |
625 ms |
22664 KB |
Output isn't correct |
| 13 |
Correct |
517 ms |
24968 KB |
Output is correct |
| 14 |
Runtime error |
144 ms |
40292 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
316 ms |
13876 KB |
Output isn't correct |
| 2 |
Runtime error |
150 ms |
44024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
430 ms |
22532 KB |
Output isn't correct |
| 4 |
Incorrect |
408 ms |
20140 KB |
Output isn't correct |
| 5 |
Incorrect |
402 ms |
19704 KB |
Output isn't correct |
| 6 |
Incorrect |
464 ms |
19704 KB |
Output isn't correct |
| 7 |
Incorrect |
414 ms |
18872 KB |
Output isn't correct |
| 8 |
Incorrect |
451 ms |
22628 KB |
Output isn't correct |
| 9 |
Runtime error |
197 ms |
47268 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
194 ms |
46488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
184 ms |
46404 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
184 ms |
44040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
175 ms |
53444 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Incorrect |
637 ms |
21364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
171 ms |
47104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
164 ms |
44048 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
177 ms |
53464 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
165 ms |
47100 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
165 ms |
46444 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
162 ms |
46328 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
156 ms |
44024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
171 ms |
53368 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
148 ms |
40524 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
