// This Program is made by Jan(Codezebra)
#include<bits/stdc++.h>
//#define int long long
//#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,q,root;
int grens=0;
vector<bool> vol;
vector<int>parent;
vector<vector<pair<int,int> > >children;
vector<int> place;
vector<int> topo;
priority_queue<int, vector<int>, greater<int> > gaten;
int find(int x){
for(int i=0;i<children[parent[x]].size();i++){
if(children[parent[x]][i].second==x){
return i;
}
}
return -1;
}
int build(int x){
// cout<<"in "<<x<<"\n";
if(children[x].empty()){
place[x]=topo.size();
topo.push_back(x);
// cout<<x<<"out\n";
return children[parent[x]][find(x)].first=x;
}
int a=x;
for(auto e:children[x]){
a=min(a,build(e.second));
}
// cout<<a<< "\n";
place[x]=topo.size();
topo.push_back(x);
// cout<<x<<"out\n";
return children[parent[x]][find(x)].first=a;
}
int roll(int x){
//cout<<x<<"*";
for(int i=01;i<children[x].size();i++){
if(!vol[children[x][i].second]){
// vol[children[x][i].second]=1;
return roll(children[x][i].second);
}
}
vol[x]=1;
return x;
}
int op1(int k){
if(k>gaten.size()){
// cout<<"wipe them all!\n";
while(!gaten.empty()){
vol[topo[gaten.top()]]=0;
gaten.pop();
}
// cout<<"done that, been there\n";
// cout<<"couting: ";
for(int i=grens;i<k+grens;i++){
// cout<<i<<" ";
vol[topo[i]]=1;
}
// cout<<"go!\n";
grens+=k;
return topo[grens-1];
}
else{
// cout<<"just snipe some!\n";
for(int i=0;i<k;i++){
vol[topo[gaten.top()]]=1;
if(i==k-1){
int pp=gaten.top();
gaten.pop();
return topo[pp];
}
gaten.pop();
}
}
/*
for(int i=1;i<k;i++){
// cout<<roll(root)<<" ";
int qq=roll(root);
}
return roll(root);
*/
}
int op2(int x){
int a=x;
int prev=x;
for(int i=0;;i++){
if(!vol[parent[a]]){
vol[a]=0;
gaten.push(place[a]);
return i;
}
a=parent[a];
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
children.resize(n+1);
parent.resize(n+1,0);
vol.resize(n+1,0);
place.resize(n+1,0);
for(int i=1;i<=n;i++){
int p;
cin>>p;
parent[i]=p;
children[p].push_back({0,i});
}
root=children[0][0].second;
build(root);
topo.clear();
for(int i=0;i<n;i++){
sort(children[i].begin(),children[i].end());
}
build(root);
/* for(int e:topo){
cout<<e<<" ";
}cout<<"\n";*/
int ans[n];
for(int i=0;i<q;i++){
int type;
cin>>type;
if(type==1){
int k;
cin>>k;
cout<<op1(k)<<"\n";
}
else{
int x;
cin>>x;
cout<<op2(x)<<"\n";
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'int find(int)':
ballmachine.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<children[parent[x]].size();i++){
~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int roll(int)':
ballmachine.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=01;i<children[x].size();i++){
~^~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int op1(int)':
ballmachine.cpp:62:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(k>gaten.size()){
~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int op2(int)':
ballmachine.cpp:102:6: warning: unused variable 'prev' [-Wunused-variable]
int prev=x;
^~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:144:6: warning: unused variable 'ans' [-Wunused-variable]
int ans[n];
^~~
ballmachine.cpp: In function 'int op1(int)':
ballmachine.cpp:98:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1071 ms |
384 KB |
Time limit exceeded |
2 |
Execution timed out |
1068 ms |
4088 KB |
Time limit exceeded |
3 |
Correct |
57 ms |
4216 KB |
Output is correct |
4 |
Execution timed out |
1064 ms |
384 KB |
Time limit exceeded |
5 |
Execution timed out |
1085 ms |
384 KB |
Time limit exceeded |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Execution timed out |
1085 ms |
384 KB |
Time limit exceeded |
8 |
Execution timed out |
1073 ms |
384 KB |
Time limit exceeded |
9 |
Execution timed out |
1068 ms |
640 KB |
Time limit exceeded |
10 |
Correct |
16 ms |
1280 KB |
Output is correct |
11 |
Execution timed out |
1049 ms |
4088 KB |
Time limit exceeded |
12 |
Correct |
61 ms |
4216 KB |
Output is correct |
13 |
Incorrect |
96 ms |
3996 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
2816 KB |
Output is correct |
2 |
Execution timed out |
1067 ms |
8756 KB |
Time limit exceeded |
3 |
Execution timed out |
1064 ms |
5876 KB |
Time limit exceeded |
4 |
Runtime error |
31 ms |
6136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
5 |
Execution timed out |
1073 ms |
2816 KB |
Time limit exceeded |
6 |
Incorrect |
58 ms |
3064 KB |
Output isn't correct |
7 |
Execution timed out |
1075 ms |
2304 KB |
Time limit exceeded |
8 |
Correct |
27 ms |
2944 KB |
Output is correct |
9 |
Execution timed out |
1075 ms |
9396 KB |
Time limit exceeded |
10 |
Execution timed out |
1067 ms |
8812 KB |
Time limit exceeded |
11 |
Incorrect |
152 ms |
8692 KB |
Output isn't correct |
12 |
Incorrect |
288 ms |
7664 KB |
Output isn't correct |
13 |
Correct |
111 ms |
10996 KB |
Output is correct |
14 |
Execution timed out |
1076 ms |
5864 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1049 ms |
5308 KB |
Time limit exceeded |
2 |
Execution timed out |
1077 ms |
7552 KB |
Time limit exceeded |
3 |
Execution timed out |
1072 ms |
9848 KB |
Time limit exceeded |
4 |
Execution timed out |
1077 ms |
7416 KB |
Time limit exceeded |
5 |
Execution timed out |
1076 ms |
7028 KB |
Time limit exceeded |
6 |
Execution timed out |
1069 ms |
7152 KB |
Time limit exceeded |
7 |
Execution timed out |
1072 ms |
6260 KB |
Time limit exceeded |
8 |
Execution timed out |
1072 ms |
9772 KB |
Time limit exceeded |
9 |
Execution timed out |
1078 ms |
9084 KB |
Time limit exceeded |
10 |
Execution timed out |
1074 ms |
8664 KB |
Time limit exceeded |
11 |
Execution timed out |
1074 ms |
8572 KB |
Time limit exceeded |
12 |
Execution timed out |
1087 ms |
7416 KB |
Time limit exceeded |
13 |
Execution timed out |
1069 ms |
12148 KB |
Time limit exceeded |
14 |
Execution timed out |
1069 ms |
5988 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1065 ms |
9048 KB |
Time limit exceeded |
2 |
Execution timed out |
1076 ms |
7412 KB |
Time limit exceeded |
3 |
Correct |
128 ms |
12400 KB |
Output is correct |
4 |
Execution timed out |
1074 ms |
9040 KB |
Time limit exceeded |
5 |
Execution timed out |
1054 ms |
9040 KB |
Time limit exceeded |
6 |
Incorrect |
123 ms |
8688 KB |
Output isn't correct |
7 |
Execution timed out |
1074 ms |
7576 KB |
Time limit exceeded |
8 |
Correct |
160 ms |
12272 KB |
Output is correct |
9 |
Execution timed out |
1070 ms |
5876 KB |
Time limit exceeded |