Submission #102323

#	Time	Username	Problem	Language	Result	Execution time	Memory
102323		janlivens	Ball Machine (BOI13_ballmachine)	C++14	29.84 / 100	1085 ms	11000 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;

int root;

vector<bool> vol;
vector<int>parent;
vector<vector<pair<int,int> > >children;
//vector<int>m;

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<<x<<" % ";
	if(children[x].empty()){
		//cout<<"0";
		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";
	return children[parent[x]][find(x)].first=a;
}

int roll(int x){
	//cout<<x<<"*";
	for(int i=children[x].size()-1;i>=0;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){
	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;
			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);
	
	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;
//	cout<<"root: "<<root<<"\n";
//	cout<<"input\n";
	
/*	for(int e:parent){
		cout<<e<<" ";
	}cout<<"\n";
	*/
	
	build(root);
//	cout<<"build\n";
	
	for(int i=0;i<n;i++){
		sort(children[i].begin(),children[i].end(), greater<pair<int,int> >());
	}
	vector<int> ans;
	for(int i=0;i<q;i++){
		int type;
		cin>>type;
		if(type==1){
			int k;
			cin>>k;
			ans.push_back(op1(k));
		//	cout<<op1(k)<<"\n";
		}
		else if(type==2){
			int x;
			cin>>x;
			ans.push_back(op2(x));
		//	cout<<op2(x)<<"\n";
		}
	}
	for(int e:ans){
		cout<<e<<"\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 op1(int)':
ballmachine.cpp:55:6: warning: unused variable 'qq' [-Wunused-variable]
  int qq=roll(root);
      ^~
ballmachine.cpp: In function 'int op2(int)':
ballmachine.cpp:62:6: warning: unused variable 'prev' [-Wunused-variable]
  int prev=x;
      ^~~~

• Subtask 1: 25 / 25
• Subtask 2: 4.285714285714286 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0.5555555555555556 / 5