oj.uz

Submission #30978

# Submission time Handle Problem Language Result Execution time Memory
30978 2017-08-02T14:32:06 Z Mamnoon_Siam Ball Machine (BOI13_ballmachine) C++14
27.21 / 100
 979 ms 30072 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define lc (node<<1)
#define rc ((node<<1)|1)
#define mid ((b+e)>>1)
 
int par[100010], T[400040];
vector<int> v[100010]; int root;
int cntr=1; int a[100010], depth[100010];
bool all[400040]; int n, Q;
int table[20][100010], where[100010];
int auxilary[100010];
 
int dfs(int u) {
	if(v[u].size()==0) return u;
	vector<pair<int, int>> temp;
	for(auto b : v[u]) temp.push_back({dfs(b), b});
	sort(temp.begin(), temp.end()); v[u].clear();
	for(auto b : temp) v[u].push_back(b.second);
	return min(u, temp[0].first);
}
 
void make_arr(int u) {
	if(v[u].size()==0) { a[cntr++]=u; return ; }
	for(auto b : v[u]) make_arr(b);
	a[cntr++] = u; return ;
}
 
void calc_depth(int u, int d) { depth[u]=d; for(auto b : v[u]) calc_depth(b, d+1); }
 
void remove(int node, int b, int e, int pos) {
	if(e<pos || b>pos) return ;
	if(b==e) { all[node]=false; T[node]=0; return ; }
	if(all[node]) {
		all[lc]=all[rc]=true; all[node]=false;
		T[lc]=mid-b+1; T[rc]=e-mid;
	}
	remove(lc, b, mid, pos); remove(rc, mid+1, e, pos);
	T[node]=T[lc]+T[rc];
}
 
void update(int node, int b, int e, int i, int j) {
	if(b>j || e<i) return ;
	if(i<=b && e<=j) { all[node]=true; T[node]=e-b+1; return ; }
	update(lc, b, mid, i, j); update(rc, mid+1, e, i, j);
	T[node]=T[lc]+T[rc];
}
 
int range_query(int node, int b, int e, int i, int j) {
	if(e<i || b>j) return 0;
	if(i<=b && e<=j) return T[node];
	if(all[node]==true) {
		all[lc]=all[rc]=true; all[node]=false;
		T[lc]=mid-b+1; T[rc]=e-mid;
	}
	return range_query(lc, b, mid, i, j)+range_query(rc, mid+1, e, i, j);
}
 
int single_query(int pos) {
	if(pos==0 || pos==-1) return 0;
	return range_query(1, 1, n, pos, pos);
}
 
void make_table() {
	for(int i=1; i<=n; i++) table[0][i]= par[i]!=0 ? par[i] : -1 ;
	for(int i=1; i<19; i++) {
		for(int j=1; j<=n; j++) {
			int md=table[i-1][j];
			if(md!=-1) {
				table[i][j]=table[i-1][md];
			}
		}
	}
}
 
int BS(int x) {
	int lo=1, hi=n; int middle=(hi+lo)>>1;
	int ans=0;
	while(lo<=hi) {
		int ret=range_query(1, 1, n, 1, middle);
		ret=middle-ret;
		if(ret>=x) ans=middle, hi=middle-1;
		else lo=middle+1;
		middle=(hi+lo)>>1;
	}
	return ans;
}
 
int lift_it(int x) {
	for(int i=18; i>=0; i--) {
		if(table[i][x]!=-1) {
			int ret=single_query(where[table[i][x]]);
			if(ret==1) x=table[i][x];
		}
	}
	return x;
}
 
int main () {
	cin>>n>>Q; memset(table, -1, sizeof(table));
	for(int i=1; i<=n; i++) {
		cin>>par[i]; if(par[i]==0) root=i;
		v[par[i]].push_back(i);
	}
	dfs(root); make_arr(root);
	make_table(); calc_depth(root, 1);
	for(int i=1; i<=n; i++) where[a[i]]=i;
	for(int i=1; i<=Q; i++) {
		int op, x; cin>>op>>x;
		if(op==1) {
			int temp=BS(x);
			cout<<a[temp]<<endl;
			update(1, 1, n, 1, temp);
		}
		else {
			int temp=lift_it(x);
			cout<<depth[x]-depth[temp]<<endl;
			remove(1, 1, n, where[temp]);
		}
	}
	return 0;
}

Subtask #1
15.3846153846 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16088 KB Output is correct
2 Runtime error 369 ms 17144 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 289 ms 17144 KB Execution timed out (wall clock limit exceeded)
4 Correct 0 ms 16088 KB Output is correct
5 Correct 3 ms 16088 KB Output is correct
6 Correct 0 ms 16088 KB Output is correct
7 Correct 0 ms 16088 KB Output is correct
8 Correct 3 ms 16088 KB Output is correct
9 Correct 39 ms 16220 KB Output is correct
10 Correct 59 ms 16352 KB Output is correct
11 Runtime error 403 ms 17144 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 256 ms 17144 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 286 ms 17144 KB Execution timed out (wall clock limit exceeded)

Subtask #2
2.14285714286 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 266 ms 18484 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 683 ms 23800 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 279 ms 18496 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 506 ms 18392 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 466 ms 18388 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 486 ms 18392 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 556 ms 17376 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 266 ms 18492 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 786 ms 23812 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 659 ms 23804 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 619 ms 23804 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 579 ms 20748 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 353 ms 28392 KB Execution timed out (wall clock limit exceeded)
14 Correct 329 ms 18496 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 19884 KB Output is correct
2 Runtime error 459 ms 20944 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 536 ms 27224 KB Execution timed out (wall clock limit exceeded)
4 Correct 413 ms 22320 KB Output is correct
5 Runtime error 566 ms 22320 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 549 ms 22320 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 676 ms 19868 KB Execution timed out (wall clock limit exceeded)
8 Correct 596 ms 27220 KB Output is correct
9 Runtime error 626 ms 23804 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 653 ms 23804 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 573 ms 23812 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 599 ms 20944 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 473 ms 30072 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 326 ms 18500 KB Execution timed out (wall clock limit exceeded)

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 23812 KB Output is correct
2 Runtime error 573 ms 20940 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 413 ms 30068 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 786 ms 23808 KB Execution timed out (wall clock limit exceeded)
5 Correct 979 ms 23808 KB Output is correct
6 Runtime error 599 ms 23808 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 549 ms 20944 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 389 ms 30064 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 309 ms 18500 KB Execution timed out (wall clock limit exceeded)