oj.uz

답안 #102323

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102323 2019-03-24T10:27:07 Z janlivens Ball Machine (BOI13_ballmachine) C++14
29.8413 / 100
 1000 ms 11000 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){
	//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

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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 85 ms 3960 KB Output is correct
3 Correct 47 ms 4084 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 5 ms 528 KB Output is correct
10 Correct 17 ms 1280 KB Output is correct
11 Correct 97 ms 3912 KB Output is correct
12 Correct 69 ms 4056 KB Output is correct
13 Correct 63 ms 3952 KB Output is correct

Subtask #2
4.28571428571 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 2460 KB Time limit exceeded
2 Execution timed out 1076 ms 7544 KB Time limit exceeded
3 Correct 907 ms 5416 KB Output is correct
4 Execution timed out 1074 ms 2688 KB Time limit exceeded
5 Execution timed out 1080 ms 2560 KB Time limit exceeded
6 Execution timed out 1066 ms 2560 KB Time limit exceeded
7 Execution timed out 1073 ms 2048 KB Time limit exceeded
8 Execution timed out 1069 ms 2412 KB Time limit exceeded
9 Execution timed out 1074 ms 7928 KB Time limit exceeded
10 Execution timed out 1063 ms 7548 KB Time limit exceeded
11 Execution timed out 1062 ms 7544 KB Time limit exceeded
12 Execution timed out 1068 ms 6272 KB Time limit exceeded
13 Execution timed out 1067 ms 9848 KB Time limit exceeded
14 Correct 965 ms 5488 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1072 ms 4088 KB Time limit exceeded
2 Execution timed out 1075 ms 6392 KB Time limit exceeded
3 Execution timed out 1065 ms 8824 KB Time limit exceeded
4 Execution timed out 1080 ms 6392 KB Time limit exceeded
5 Execution timed out 1072 ms 6140 KB Time limit exceeded
6 Execution timed out 1076 ms 6136 KB Time limit exceeded
7 Execution timed out 1071 ms 5112 KB Time limit exceeded
8 Execution timed out 1080 ms 8824 KB Time limit exceeded
9 Execution timed out 1081 ms 7928 KB Time limit exceeded
10 Execution timed out 1074 ms 7544 KB Time limit exceeded
11 Execution timed out 1064 ms 7548 KB Time limit exceeded
12 Execution timed out 1066 ms 6392 KB Time limit exceeded
13 Execution timed out 1080 ms 11000 KB Time limit exceeded
14 Execution timed out 1085 ms 4728 KB Time limit exceeded

Subtask #4
0.555555555556 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1067 ms 7928 KB Time limit exceeded
2 Execution timed out 1071 ms 6392 KB Time limit exceeded
3 Execution timed out 1074 ms 11000 KB Time limit exceeded
4 Execution timed out 1072 ms 7928 KB Time limit exceeded
5 Execution timed out 1073 ms 7544 KB Time limit exceeded
6 Execution timed out 1070 ms 7544 KB Time limit exceeded
7 Execution timed out 1075 ms 6392 KB Time limit exceeded
8 Execution timed out 1075 ms 11000 KB Time limit exceeded
9 Correct 908 ms 5548 KB Output is correct