oj.uz

Submission #30981

# Submission time Handle Problem Language Result Execution time Memory
30981 2017-08-02T14:53:39 Z Mamnoon_Siam Ball Machine (BOI13_ballmachine) C++14
25.3846 / 100
 853 ms 29680 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 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; cntr++; return ; }
	for(auto b : v[u]) make_arr(b);
	a[cntr] = u; cntr++; 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]);
		}
	}
	//system("pause");
	return 0;
}

Subtask #1
15.3846153846 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15696 KB Output is correct
2 Runtime error 369 ms 16752 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 216 ms 16752 KB Execution timed out (wall clock limit exceeded)
4 Correct 0 ms 15696 KB Output is correct
5 Correct 3 ms 15696 KB Output is correct
6 Correct 0 ms 15696 KB Output is correct
7 Correct 9 ms 15696 KB Output is correct
8 Correct 6 ms 15696 KB Output is correct
9 Correct 29 ms 15828 KB Output is correct
10 Correct 103 ms 15960 KB Output is correct
11 Runtime error 319 ms 16752 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 219 ms 16752 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 283 ms 16752 KB Execution timed out (wall clock limit exceeded)

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 ms 18096 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 509 ms 23408 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 249 ms 18104 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 409 ms 18004 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 336 ms 17996 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 416 ms 18000 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 389 ms 16984 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 259 ms 18096 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 599 ms 23416 KB Execution timed out (wall clock limit exceeded)
10 Correct 839 ms 23408 KB Output is correct
11 Runtime error 533 ms 23408 KB Execution timed out (wall clock limit exceeded)
12 Correct 709 ms 20352 KB Output is correct
13 Runtime error 299 ms 27992 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 263 ms 18104 KB Execution timed out (wall clock limit exceeded)

Subtask #3
5.71428571429 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 19500 KB Output is correct
2 Runtime error 716 ms 20552 KB Execution timed out (wall clock limit exceeded)
3 Correct 626 ms 26832 KB Output is correct
4 Runtime error 486 ms 21928 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 506 ms 21924 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 689 ms 21924 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 596 ms 19472 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 573 ms 26832 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 396 ms 23416 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 683 ms 23412 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 783 ms 23412 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 566 ms 20552 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 563 ms 29680 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 329 ms 18108 KB Execution timed out (wall clock limit exceeded)

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 639 ms 23420 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 616 ms 20544 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 306 ms 29680 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 619 ms 23420 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 853 ms 23416 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 696 ms 23412 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 666 ms 20548 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 516 ms 29676 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 243 ms 18108 KB Execution timed out (wall clock limit exceeded)