oj.uz

Submission #30980

# Submission time Handle Problem Language Result Execution time Memory
30980 2017-08-02T14:47:13 Z Mamnoon_Siam Ball Machine (BOI13_ballmachine) C++14
47.8632 / 100
 1000 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; 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);
	}
	for(int i=1; i<=1000000000; i++) { i++; 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
17.3076923077 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15696 KB Output is correct
2 Runtime error 353 ms 16752 KB Execution timed out (wall clock limit exceeded)
3 Correct 303 ms 16752 KB Output is correct
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 6 ms 15696 KB Output is correct
8 Correct 3 ms 15696 KB Output is correct
9 Correct 49 ms 15828 KB Output is correct
10 Correct 133 ms 15960 KB Output is correct
11 Runtime error 386 ms 16752 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 299 ms 16752 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 436 ms 16752 KB Execution timed out (wall clock limit exceeded)

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 18096 KB Output is correct
2 Execution timed out 1000 ms 23408 KB Execution timed out
3 Runtime error 299 ms 18104 KB Execution timed out (wall clock limit exceeded)
4 Correct 413 ms 18008 KB Output is correct
5 Correct 606 ms 17996 KB Output is correct
6 Correct 579 ms 17996 KB Output is correct
7 Correct 586 ms 16984 KB Output is correct
8 Correct 216 ms 18096 KB Output is correct
9 Runtime error 619 ms 23416 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 659 ms 23404 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 549 ms 23408 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 783 ms 20352 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 583 ms 27996 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 266 ms 18104 KB Execution timed out (wall clock limit exceeded)

Subtask #3
17.1428571429 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 19496 KB Output is correct
2 Correct 786 ms 20552 KB Output is correct
3 Runtime error 646 ms 26828 KB Execution timed out (wall clock limit exceeded)
4 Correct 639 ms 21928 KB Output is correct
5 Runtime error 689 ms 21928 KB Execution timed out (wall clock limit exceeded)
6 Correct 736 ms 21928 KB Output is correct
7 Correct 516 ms 19480 KB Output is correct
8 Runtime error 536 ms 26824 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 526 ms 23416 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 706 ms 23420 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 563 ms 23416 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 666 ms 20548 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 949 ms 29680 KB Execution timed out (wall clock limit exceeded)
14 Correct 513 ms 18108 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 536 ms 23416 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 759 ms 20548 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 526 ms 29676 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 689 ms 23420 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 676 ms 23416 KB Execution timed out (wall clock limit exceeded)
6 Correct 813 ms 23416 KB Output is correct
7 Runtime error 806 ms 20548 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 403 ms 29676 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 306 ms 18108 KB Execution timed out (wall clock limit exceeded)