Submission #943989

#	Time	Username	Problem	Language	Result	Execution time	Memory
943989		tamir1	Ball Machine (BOI13_ballmachine)	C++17	0 / 100	13 ms	21852 KiB

ballmachine

#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
int root,n,q,i,j,type,x,a[100005],jump[20][100005],sz[100005],dist[100005];
vector<int> v[100005];
bitset<100005> ball;
void dfs(int k){
	a[k]=k;
	sz[k]=1;
	for(int i:v[k]){
		dist[i]=dist[k]+1;
		dfs(i);
		a[k]=min(a[k],a[i]);
		sz[k]+=sz[i];
	}
}
int find(int x){
	if(ball[jump[x][0]]==0) return x;
	return find(jump[x][0]);
}
int update(int x){
	int mx=1e8,idx=0;
	for(int i:v[x]){
		if(a[i]<mx && !ball[i]){
			mx=a[i];
			idx=i;
		}
	}
	if(idx!=0) return update(idx);
	else{
		ball[x]=1;
		return x;
	}
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q;
	for(i=1;i<=n;i++){
		cin >> jump[i][0];
		if(jump[i][0]==0) root=i;
		else v[jump[i][0]].push_back(i);
	}
	dfs(root);
	for(j=1;j<=18;j++){
		for(i=1;i<=n;i++){
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}
	while(q--){
		cin >> type >> x;
		if(type==1){
			for(i=1;i<=x;i++){
				type=update(1);
			}
			cout << type << "\n";
		}
		else{
			type=find(x);
			ball[type]=0;
			cout << dist[x]-dist[type] << "\n";
		}
	}
}

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