Submission #30976

#	Time	Username	Problem	Language	Result	Execution time	Memory
30976		Mamnoon_Siam	Ball Machine (BOI13_ballmachine)	C++14	55.34 / 100	759 ms	30072 KiB

ballmachine

#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.23076923076923 / 25
• Subtask 2: 15 / 30
• Subtask 3: 20 / 40
• Subtask 4: 1.1111111111111112 / 5