oj.uz

답안 #102312

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102312 2019-03-24T09:42:15 Z janlivens Ball Machine (BOI13_ballmachine) C++14
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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Incorrect 58 ms 3576 KB Output isn't correct
3 Correct 43 ms 3576 KB Output is correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Incorrect 3 ms 384 KB Output isn't correct
6 Incorrect 3 ms 384 KB Output isn't correct
7 Incorrect 3 ms 384 KB Output isn't correct
8 Incorrect 3 ms 384 KB Output isn't correct
9 Incorrect 8 ms 512 KB Output isn't correct
10 Incorrect 13 ms 1272 KB Output isn't correct
11 Incorrect 49 ms 3320 KB Output isn't correct
12 Correct 49 ms 3584 KB Output is correct
13 Incorrect 56 ms 3456 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1058 ms 2280 KB Time limit exceeded
2 Execution timed out 1062 ms 6008 KB Time limit exceeded
3 Correct 52 ms 4988 KB Output is correct
4 Incorrect 34 ms 2048 KB Output isn't correct
5 Incorrect 33 ms 1920 KB Output isn't correct
6 Incorrect 27 ms 1920 KB Output isn't correct
7 Incorrect 30 ms 1892 KB Output isn't correct
8 Execution timed out 1059 ms 2296 KB Time limit exceeded
9 Execution timed out 1070 ms 7928 KB Time limit exceeded
10 Execution timed out 1075 ms 6008 KB Time limit exceeded
11 Incorrect 82 ms 5496 KB Output isn't correct
12 Incorrect 59 ms 5240 KB Output isn't correct
13 Execution timed out 1074 ms 6620 KB Time limit exceeded
14 Correct 66 ms 4852 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1067 ms 3840 KB Time limit exceeded
2 Execution timed out 1077 ms 6016 KB Time limit exceeded
3 Execution timed out 1072 ms 6140 KB Time limit exceeded
4 Incorrect 43 ms 4864 KB Output isn't correct
5 Incorrect 48 ms 4480 KB Output isn't correct
6 Incorrect 43 ms 4472 KB Output isn't correct
7 Execution timed out 1075 ms 4984 KB Time limit exceeded
8 Execution timed out 1078 ms 6016 KB Time limit exceeded
9 Incorrect 86 ms 6392 KB Output isn't correct
10 Incorrect 57 ms 6008 KB Output isn't correct
11 Execution timed out 1041 ms 5496 KB Time limit exceeded
12 Execution timed out 1062 ms 6008 KB Time limit exceeded
13 Execution timed out 1061 ms 7032 KB Time limit exceeded
14 Incorrect 62 ms 4844 KB Output isn't correct

Subtask #4
0.555555555556 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 73 ms 6404 KB Output isn't correct
2 Execution timed out 1077 ms 6264 KB Time limit exceeded
3 Execution timed out 1066 ms 9720 KB Time limit exceeded
4 Incorrect 66 ms 6264 KB Output isn't correct
5 Incorrect 78 ms 5960 KB Output isn't correct
6 Execution timed out 1081 ms 7032 KB Time limit exceeded
7 Execution timed out 1082 ms 6236 KB Time limit exceeded
8 Execution timed out 1076 ms 9720 KB Time limit exceeded
9 Correct 75 ms 4848 KB Output is correct