oj.uz

Submission #30979

# Submission time Handle Problem Language Result Execution time Memory
30979 2017-08-02T14:43:57 Z Mamnoon_Siam Ball Machine (BOI13_ballmachine) C++14
36.9902 / 100
 939 ms 29676 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<=100000000; 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 389 ms 16752 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 306 ms 16752 KB Execution timed out (wall clock limit exceeded)
4 Correct 3 ms 15696 KB Output is correct
5 Correct 3 ms 15696 KB Output is correct
6 Correct 3 ms 15696 KB Output is correct
7 Correct 6 ms 15696 KB Output is correct
8 Correct 6 ms 15696 KB Output is correct
9 Correct 23 ms 15828 KB Output is correct
10 Correct 129 ms 15960 KB Output is correct
11 Runtime error 309 ms 16752 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 239 ms 16752 KB Execution timed out (wall clock limit exceeded)
13 Correct 466 ms 16752 KB Output is correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 233 ms 18096 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 756 ms 23408 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 296 ms 18104 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 353 ms 18004 KB Execution timed out (wall clock limit exceeded)
5 Correct 639 ms 18000 KB Output is correct
6 Runtime error 546 ms 18000 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 503 ms 16988 KB Execution timed out (wall clock limit exceeded)
8 Correct 233 ms 18096 KB Output is correct
9 Runtime error 743 ms 23420 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 586 ms 23408 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 816 ms 23408 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 646 ms 20352 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 289 ms 27996 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 323 ms 18104 KB Execution timed out (wall clock limit exceeded)

Subtask #3
14.2857142857 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 19492 KB Output is correct
2 Runtime error 563 ms 20548 KB Execution timed out (wall clock limit exceeded)
3 Correct 573 ms 26832 KB Output is correct
4 Runtime error 533 ms 21924 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 776 ms 21924 KB Execution timed out (wall clock limit exceeded)
6 Correct 809 ms 21924 KB Output is correct
7 Runtime error 599 ms 19476 KB Execution timed out (wall clock limit exceeded)
8 Correct 639 ms 26832 KB Output is correct
9 Runtime error 383 ms 23420 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 526 ms 23412 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 616 ms 23416 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 753 ms 20552 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 766 ms 29676 KB Execution timed out (wall clock limit exceeded)
14 Correct 376 ms 18108 KB Output is correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 886 ms 23420 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 779 ms 20552 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 376 ms 29676 KB Execution timed out (wall clock limit exceeded)
4 Correct 683 ms 23416 KB Output is correct
5 Runtime error 796 ms 23412 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 939 ms 23416 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 789 ms 20552 KB Execution timed out (wall clock limit exceeded)
8 Correct 499 ms 29676 KB Output is correct
9 Runtime error 189 ms 18108 KB Execution timed out (wall clock limit exceeded)