Submission #37298

#	Time	Username	Problem	Language	Result	Execution time	Memory
37298		petros_marko	Ball Machine (BOI13_ballmachine)	C++14	41.92 / 100	219 ms	33152 KiB

ballmachine

#include<cstdio>
#include<vector>
#include<algorithm>

#define MAX_N 200000

using namespace std;

int parent[MAX_N];
int par[MAX_N][20];
int ball[MAX_N];
int depth[MAX_N];
vector<int> adjList[MAX_N];
int minsub[MAX_N];
int root;
vector<int> euler;
int point;
int n,q;

void dfs1(int source,int d){
	minsub[source] = source;
	depth[source] = d;
	for(int i = 0; i < adjList[source].size(); i++){
		dfs1(adjList[source][i],d + 1);
		if(minsub[adjList[source][i]] < minsub[source]){
			minsub[source] = minsub[adjList[source][i]];
		}
	}
}

void dfs2(int source){
	for(int i = 0; i < adjList[source].size(); i++){
		dfs2(adjList[source][i]);	
	}
	euler.push_back(source);
}

bool cmp( int node1, int node2 ) {
	return minsub[ node1 ] < minsub[ node2 ];
}

void precompute(){
	dfs1(root,1);	
	for( int i = 1; i <= n; i++ ) sort( adjList[ i ].begin(), adjList[ i ].end(), cmp );
	dfs2(root);
	for(int i = 1; i <= n; i++){
		par[i][0] = parent[i];
	}
	for(int k = 1; (1<<k) <= n; k++){
		for(int i = 1; i <= n; i++){
			par[i][k] = par[par[i][k-1]][k-1];
		}
	}
}

int add_k(int k){
	while(k--)ball[euler[point++]] = 1;
	return euler[point-1];
}

int remove_ball(int x){
	int lg = 0, d = depth[ x ];
	while((1<<lg) <= depth[x]){
		lg++;	
	}
	lg--;
	for( int i = lg; i >= 0; i-- ) {
		if( par[ x ][ i ] == 0 ) continue;
		if( ball[ par[ x ][ i ] ] ) x = par[ x ][ i ];
	}
	ball[x] = 0;
	return d - depth[x];
}

int main(){
	
	scanf("%d%d",&n,&q);
	
	for(int i = 1; i <= n; i++){
		scanf("%d",parent + i);		
		adjList[parent[i]].push_back(i);
		if(parent[i] == 0)
			root = i;
	}
	
	precompute();

	for(int i = 0; i < q; i++){
		int qt,ans;
		scanf("%d",&qt);
		if(qt == 1){
			int k;
			scanf("%d",&k);
			ans = add_k(k);
		}
		else{
			int x;
			scanf("%d",&x);
			ans = remove_ball(x);
		}
		printf("%d\n",ans);
	}

	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs1(int, int)':
ballmachine.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adjList[source].size(); i++){
                   ^
ballmachine.cpp: In function 'void dfs2(int)':
ballmachine.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adjList[source].size(); i++){
                   ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:77:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
                     ^
ballmachine.cpp:80:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",parent + i);  
                         ^
ballmachine.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&qt);
                  ^
ballmachine.cpp:93:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&k);
                  ^
ballmachine.cpp:98:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
                  ^

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