oj.uz

Submission #37298

# Submission time Handle Problem Language Result Execution time Memory
37298 2017-12-23T16:06:42 Z petros_marko Ball Machine (BOI13_ballmachine) C++14
41.9231 / 100
 219 ms 33152 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 24608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 53 ms 26096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 83 ms 26096 KB Output isn't correct
4 Runtime error 0 ms 24608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 24608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Correct 0 ms 24608 KB Output is correct
7 Incorrect 0 ms 24608 KB Output isn't correct
8 Incorrect 0 ms 24608 KB Output isn't correct
9 Incorrect 3 ms 24740 KB Output isn't correct
10 Incorrect 23 ms 25004 KB Output isn't correct
11 Runtime error 59 ms 26096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 66 ms 26096 KB Output isn't correct
13 Runtime error 56 ms 26096 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 26132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 133 ms 29632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 79 ms 27016 KB Output isn't correct
4 Runtime error 26 ms 26108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 33 ms 25976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 39 ms 25980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 23 ms 25624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 33 ms 26132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 186 ms 30052 KB Output isn't correct
10 Runtime error 149 ms 29624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Incorrect 166 ms 29624 KB Output isn't correct
12 Incorrect 183 ms 28384 KB Output isn't correct
13 Incorrect 166 ms 32224 KB Output isn't correct
14 Incorrect 113 ms 27016 KB Output isn't correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 27312 KB Output is correct
2 Correct 216 ms 28460 KB Output is correct
3 Correct 143 ms 31588 KB Output is correct
4 Correct 133 ms 29108 KB Output is correct
5 Correct 153 ms 28776 KB Output is correct
6 Correct 149 ms 28780 KB Output is correct
7 Correct 143 ms 27844 KB Output is correct
8 Correct 146 ms 31584 KB Output is correct
9 Correct 199 ms 30052 KB Output is correct
10 Correct 216 ms 29636 KB Output is correct
11 Correct 219 ms 29636 KB Output is correct
12 Correct 199 ms 28456 KB Output is correct
13 Correct 216 ms 33152 KB Output is correct
14 Correct 116 ms 27020 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 179 ms 30048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 219 ms 28460 KB Output isn't correct
3 Incorrect 153 ms 33152 KB Output isn't correct
4 Runtime error 169 ms 30048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 216 ms 29636 KB Output isn't correct
6 Incorrect 166 ms 29636 KB Output isn't correct
7 Incorrect 179 ms 28456 KB Output isn't correct
8 Incorrect 149 ms 33148 KB Output isn't correct
9 Incorrect 86 ms 27020 KB Output isn't correct