oj.uz

Submission #30878

# Submission time Handle Problem Language Result Execution time Memory
30878 2017-07-29T19:51:17 Z Mamnoon_Siam Ball Machine (BOI13_ballmachine) C++14
15.2747 / 100
 909 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; where[u]=cntr-1; 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<=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
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 15696 KB Output isn't correct
2 Incorrect 489 ms 16752 KB Output isn't correct
3 Incorrect 299 ms 16752 KB Output isn't correct
4 Incorrect 6 ms 15696 KB Output isn't correct
5 Incorrect 0 ms 15696 KB Output isn't correct
6 Correct 0 ms 15696 KB Output is correct
7 Correct 3 ms 15696 KB Output is correct
8 Incorrect 9 ms 15696 KB Output isn't correct
9 Incorrect 39 ms 15828 KB Output isn't correct
10 Incorrect 76 ms 15960 KB Output isn't correct
11 Incorrect 433 ms 16752 KB Output isn't correct
12 Runtime error 186 ms 16752 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 373 ms 16752 KB Execution timed out (wall clock limit exceeded)

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 266 ms 18092 KB Output isn't correct
2 Runtime error 909 ms 23408 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 326 ms 18104 KB Execution timed out (wall clock limit exceeded)
4 Incorrect 419 ms 18004 KB Output isn't correct
5 Incorrect 596 ms 17996 KB Output isn't correct
6 Runtime error 603 ms 18000 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 359 ms 16988 KB Execution timed out (wall clock limit exceeded)
8 Incorrect 309 ms 18100 KB Output isn't correct
9 Runtime error 583 ms 23416 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 556 ms 23412 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 759 ms 23408 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 656 ms 20352 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 489 ms 27992 KB Execution timed out (wall clock limit exceeded)
14 Incorrect 353 ms 18104 KB Output isn't correct

Subtask #3
11.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 19492 KB Output is correct
2 Runtime error 816 ms 20548 KB Execution timed out (wall clock limit exceeded)
3 Correct 686 ms 26832 KB Output is correct
4 Runtime error 436 ms 21928 KB Execution timed out (wall clock limit exceeded)
5 Correct 623 ms 21928 KB Output is correct
6 Runtime error 629 ms 21928 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 659 ms 19476 KB Execution timed out (wall clock limit exceeded)
8 Correct 576 ms 26824 KB Output is correct
9 Runtime error 359 ms 23420 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 606 ms 23416 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 576 ms 23416 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 643 ms 20548 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 686 ms 29672 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 356 ms 18108 KB Execution timed out (wall clock limit exceeded)

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 683 ms 23416 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 639 ms 20548 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 479 ms 29680 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 613 ms 23412 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 693 ms 23416 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 673 ms 23416 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 556 ms 20548 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 479 ms 29680 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 259 ms 18108 KB Execution timed out (wall clock limit exceeded)