Submission #36539

#	Time	Username	Problem	Language	Result	Execution time	Memory
36539		Dat160601	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	316 ms	34472 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
int n,q;
int par[100007],mi[100007],root,num[100007],cnt=0;
int op,x;
int p[20][100007];
bool stat[100007];
vector <int> edge[100007],edge2[100007];
priority_queue < pair<int,int> , vector < pair<int,int> > , greater < pair<int,int> > > pr;
void read(int &k){
	int x;
	scanf("%d",&x);
	k=x;
}
void print(int x){
	printf("%d\n",x);
}
void dfs(int u){
	vector < pair<int,int> > cur;
	mi[u]=u;
	for(int i=0;i<(int)edge[u].size();i++){
		int v=edge[u][i];
		if(v==par[u]) continue;
		dfs(v);
		mi[u]=min(mi[u],mi[v]);
		cur.pb(mp(mi[v],v));
	}
	sort(cur.begin(),cur.end());
	for(int i=0;i<(int)cur.size();i++){
		edge2[u].pb(cur[i].se);
	}
}
void dfs2(int u){
	for(int i=0;i<(int)edge2[u].size();i++){
		int v=edge2[u][i];
		if(v==par[u]) continue;
		dfs2(v);
	}
	cnt++;
	num[u]=cnt;
}
int main(){
	read(n);
	read(q);
	for(int i=1;i<=n;i++){
		read(par[i]);
		edge[par[i]].pb(i);
		p[0][i]=par[i];
		if(par[i]==0) root=i;
		mi[i]=1e9;
	}
	dfs(root);
	dfs2(root);
	for(int i=1;i<=n;i++) pr.push(mp(num[i],i));
	for(int i=1;i<=19;i++){
		for(int j=1;j<=n;j++){
			p[i][j]=p[i-1][p[i-1][j]];
		}
	}
	while(q--){
		read(op);
		read(x);
		if(op==1){
			int ans=0;
			while(x>0){
				x--;
				int u=pr.top().se;
				stat[u]=true;
				ans=u;
				pr.pop();
			}
			print(ans);
		}
		else{
			int ans=0;
			for(int i=19;i>=0;i--){
				int pr=p[i][x];
				if(stat[pr]){
					x=pr;
					ans+=(1<<i);
				}
			}
			stat[x]=false;
			pr.push(mp(num[x],x));
			print(ans);
		}
	}
}

Compilation message (stderr)

ballmachine.cpp: In function 'void read(int&)':
ballmachine.cpp:16:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&x);
                ^

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5