oj.uz

Submission #30976

# Submission time Handle Problem Language Result Execution time Memory
30976 2017-08-02T14:11:35 Z Mamnoon_Siam Ball Machine (BOI13_ballmachine) C++14
55.3419 / 100
 759 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; 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 BruteForceRangeUpdate(int x) {
	int c=0; int upto=0;
	for(int i=1; i<=n; i++) {
		if(auxilary[i]==0) c++;
		if(c==x) { upto=i; break; }
	}
	for(int i=1; i<=upto; i++) {
		auxilary[i]=1;
	}
	return upto;
}

void BruteForceRemove(int x) {
	auxilary[x]=0;
}

int lift_it(int x) {
	for(int i=18; i>=0; i--) {
		if(table[i][x]!=-1) {
			//int ret=single_query_BruteForce(where[table[i][x]]);
			int ret=auxilary[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);
			int temp=BruteForceRangeUpdate(x);
			cout<<a[temp]<<endl;
			//update(1, 1, n, 1, temp);
		}
		else {
			int temp=lift_it(x);
			//cout<<"temp == "<<temp<<"  ::  where == "<<where[temp]<<endl;
			cout<<depth[x]-depth[temp]<<endl;
			BruteForceRemove(where[temp]);
			//remove(1, 1, n, where[temp]);
		}
		/*cout<<"******START******"<<endl;
		for(int i=1; i<=n; i++) {
			cout<<a[i]<<" == "<<auxilary[i]<<endl;
		} cout<<"******END******"<<endl; */
	}
	//system("pause");

	return 0;
}

Subtask #1
19.2307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16088 KB Output is correct
2 Correct 383 ms 17144 KB Output is correct
3 Runtime error 206 ms 17144 KB Execution timed out (wall clock limit exceeded)
4 Correct 0 ms 16088 KB Output is correct
5 Correct 0 ms 16088 KB Output is correct
6 Correct 0 ms 16088 KB Output is correct
7 Correct 13 ms 16088 KB Output is correct
8 Correct 6 ms 16088 KB Output is correct
9 Correct 33 ms 16220 KB Output is correct
10 Correct 59 ms 16352 KB Output is correct
11 Runtime error 296 ms 17144 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 189 ms 17144 KB Execution timed out (wall clock limit exceeded)
13 Correct 413 ms 17144 KB Output is correct

Subtask #2
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 18488 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 759 ms 23800 KB Execution timed out (wall clock limit exceeded)
3 Correct 289 ms 18496 KB Output is correct
4 Correct 253 ms 18396 KB Output is correct
5 Correct 349 ms 18388 KB Output is correct
6 Correct 439 ms 18392 KB Output is correct
7 Correct 363 ms 17376 KB Output is correct
8 Runtime error 106 ms 18484 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 503 ms 23808 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 573 ms 23800 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 376 ms 23808 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 593 ms 20744 KB Execution timed out (wall clock limit exceeded)
13 Correct 343 ms 28388 KB Output is correct
14 Correct 219 ms 18496 KB Output is correct

Subtask #3
20.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 19884 KB Output is correct
2 Runtime error 519 ms 20944 KB Execution timed out (wall clock limit exceeded)
3 Correct 589 ms 27224 KB Output is correct
4 Correct 343 ms 22316 KB Output is correct
5 Correct 496 ms 22320 KB Output is correct
6 Correct 563 ms 22316 KB Output is correct
7 Runtime error 443 ms 19868 KB Execution timed out (wall clock limit exceeded)
8 Correct 523 ms 27224 KB Output is correct
9 Runtime error 373 ms 23808 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 353 ms 23804 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 639 ms 23804 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 489 ms 20940 KB Execution timed out (wall clock limit exceeded)
13 Correct 609 ms 30064 KB Output is correct
14 Runtime error 283 ms 18500 KB Execution timed out (wall clock limit exceeded)

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 23808 KB Output is correct
2 Runtime error 533 ms 20940 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 356 ms 30072 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 506 ms 23808 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 646 ms 23812 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 446 ms 23808 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 659 ms 20940 KB Execution timed out (wall clock limit exceeded)
8 Correct 426 ms 30068 KB Output is correct
9 Runtime error 216 ms 18500 KB Execution timed out (wall clock limit exceeded)