Submission #102339

#	Time	Username	Problem	Language	Result	Execution time	Memory
102339		janlivens	Ball Machine (BOI13_ballmachine)	C++14	15.23 / 100	1087 ms	12400 KiB

ballmachine

// 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 (stderr)

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]
 }
 ^

• Subtask 1: 7.6923076923076925 / 25
• Subtask 2: 6.428571428571429 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.1111111111111112 / 5