oj.uz

Submission #102339

# Submission time Handle Problem Language Result Execution time Memory
102339 2019-03-24T11:27:50 Z janlivens Ball Machine (BOI13_ballmachine) C++14
15.232 / 100
 1000 ms 12400 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,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

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

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 384 KB Time limit exceeded
2 Execution timed out 1068 ms 4088 KB Time limit exceeded
3 Correct 57 ms 4216 KB Output is correct
4 Execution timed out 1064 ms 384 KB Time limit exceeded
5 Execution timed out 1085 ms 384 KB Time limit exceeded
6 Correct 2 ms 384 KB Output is correct
7 Execution timed out 1085 ms 384 KB Time limit exceeded
8 Execution timed out 1073 ms 384 KB Time limit exceeded
9 Execution timed out 1068 ms 640 KB Time limit exceeded
10 Correct 16 ms 1280 KB Output is correct
11 Execution timed out 1049 ms 4088 KB Time limit exceeded
12 Correct 61 ms 4216 KB Output is correct
13 Incorrect 96 ms 3996 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2816 KB Output is correct
2 Execution timed out 1067 ms 8756 KB Time limit exceeded
3 Execution timed out 1064 ms 5876 KB Time limit exceeded
4 Runtime error 31 ms 6136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Execution timed out 1073 ms 2816 KB Time limit exceeded
6 Incorrect 58 ms 3064 KB Output isn't correct
7 Execution timed out 1075 ms 2304 KB Time limit exceeded
8 Correct 27 ms 2944 KB Output is correct
9 Execution timed out 1075 ms 9396 KB Time limit exceeded
10 Execution timed out 1067 ms 8812 KB Time limit exceeded
11 Incorrect 152 ms 8692 KB Output isn't correct
12 Incorrect 288 ms 7664 KB Output isn't correct
13 Correct 111 ms 10996 KB Output is correct
14 Execution timed out 1076 ms 5864 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1049 ms 5308 KB Time limit exceeded
2 Execution timed out 1077 ms 7552 KB Time limit exceeded
3 Execution timed out 1072 ms 9848 KB Time limit exceeded
4 Execution timed out 1077 ms 7416 KB Time limit exceeded
5 Execution timed out 1076 ms 7028 KB Time limit exceeded
6 Execution timed out 1069 ms 7152 KB Time limit exceeded
7 Execution timed out 1072 ms 6260 KB Time limit exceeded
8 Execution timed out 1072 ms 9772 KB Time limit exceeded
9 Execution timed out 1078 ms 9084 KB Time limit exceeded
10 Execution timed out 1074 ms 8664 KB Time limit exceeded
11 Execution timed out 1074 ms 8572 KB Time limit exceeded
12 Execution timed out 1087 ms 7416 KB Time limit exceeded
13 Execution timed out 1069 ms 12148 KB Time limit exceeded
14 Execution timed out 1069 ms 5988 KB Time limit exceeded

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 9048 KB Time limit exceeded
2 Execution timed out 1076 ms 7412 KB Time limit exceeded
3 Correct 128 ms 12400 KB Output is correct
4 Execution timed out 1074 ms 9040 KB Time limit exceeded
5 Execution timed out 1054 ms 9040 KB Time limit exceeded
6 Incorrect 123 ms 8688 KB Output isn't correct
7 Execution timed out 1074 ms 7576 KB Time limit exceeded
8 Correct 160 ms 12272 KB Output is correct
9 Execution timed out 1070 ms 5876 KB Time limit exceeded