oj.uz

Submission #102314

# Submission time Handle Problem Language Result Execution time Memory
102314 2019-03-24T09:56:15 Z janlivens Ball Machine (BOI13_ballmachine) C++11
8.68742 / 100
 1000 ms 9720 KB 
// 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){
	for(int i=children[x].size()-1;i>=0;i--){
		if(!vol[children[x][i].second]){
			return roll(children[x][i].second);
		}
	}
	vol[x]=1;
	return x;
}

int op1(int k){
	for(int i=1;i<k;i++){
		int qq=roll(1);
	}
	return roll(1);
}

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;
	root=1;
//	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> >());
	}
	for(int i=0;i<q;i++){
		int type;
		cin>>type;
		if(type==1){
			int k;
			cin>>k;
			cout<<op1(k)<<"\n";
		}
		else if(type==2){
			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 op1(int)':
ballmachine.cpp:52:7: warning: unused variable 'qq' [-Wunused-variable]
   int qq=roll(1);
       ^~
ballmachine.cpp: In function 'int op2(int)':
ballmachine.cpp:59:6: warning: unused variable 'prev' [-Wunused-variable]
  int prev=x;
      ^~~~

Subtask #1
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Incorrect 49 ms 3424 KB Output isn't correct
3 Correct 49 ms 3632 KB Output is correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Incorrect 3 ms 384 KB Output isn't correct
7 Incorrect 2 ms 384 KB Output isn't correct
8 Incorrect 3 ms 384 KB Output isn't correct
9 Incorrect 5 ms 512 KB Output isn't correct
10 Incorrect 11 ms 1024 KB Output isn't correct
11 Incorrect 61 ms 3448 KB Output isn't correct
12 Correct 58 ms 3576 KB Output is correct
13 Incorrect 46 ms 3320 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 2360 KB Time limit exceeded
2 Execution timed out 1064 ms 5988 KB Time limit exceeded
3 Correct 85 ms 4848 KB Output is correct
4 Incorrect 57 ms 2044 KB Output isn't correct
5 Incorrect 47 ms 1912 KB Output isn't correct
6 Incorrect 31 ms 1920 KB Output isn't correct
7 Incorrect 27 ms 1784 KB Output isn't correct
8 Execution timed out 1071 ms 2240 KB Time limit exceeded
9 Execution timed out 1041 ms 7860 KB Time limit exceeded
10 Execution timed out 1079 ms 6008 KB Time limit exceeded
11 Incorrect 63 ms 5628 KB Output isn't correct
12 Incorrect 62 ms 5280 KB Output isn't correct
13 Execution timed out 1042 ms 6524 KB Time limit exceeded
14 Correct 62 ms 4820 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 3836 KB Time limit exceeded
2 Execution timed out 1050 ms 6008 KB Time limit exceeded
3 Execution timed out 1062 ms 6000 KB Time limit exceeded
4 Incorrect 55 ms 4984 KB Output isn't correct
5 Incorrect 49 ms 4728 KB Output isn't correct
6 Incorrect 74 ms 4784 KB Output isn't correct
7 Execution timed out 1070 ms 4984 KB Time limit exceeded
8 Execution timed out 1069 ms 6016 KB Time limit exceeded
9 Incorrect 76 ms 6008 KB Output isn't correct
10 Incorrect 94 ms 5624 KB Output isn't correct
11 Execution timed out 1056 ms 5496 KB Time limit exceeded
12 Execution timed out 1076 ms 6016 KB Time limit exceeded
13 Execution timed out 1068 ms 7032 KB Time limit exceeded
14 Incorrect 58 ms 4848 KB Output isn't correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 6188 KB Output isn't correct
2 Execution timed out 1062 ms 6228 KB Time limit exceeded
3 Execution timed out 1069 ms 9720 KB Time limit exceeded
4 Incorrect 70 ms 6264 KB Output isn't correct
5 Incorrect 64 ms 5496 KB Output isn't correct
6 Execution timed out 1059 ms 6904 KB Time limit exceeded
7 Execution timed out 1072 ms 6264 KB Time limit exceeded
8 Execution timed out 1064 ms 9592 KB Time limit exceeded
9 Correct 50 ms 4976 KB Output is correct