Submission #944639

#	Time	Username	Problem	Language	Result	Execution time	Memory
944639		tamir1	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	142 ms	28624 KiB

ballmachine

#include<bits/stdc++.h>
#define ll int
using namespace std;
ll i,j,n,q,x,y,root,a[100005],jump[100005][21],p[100005],dist[100005];
set<ll> s;
set<ll> ::iterator it;
vector<ll> v[100005],u;
bitset<100005> ball;
void dfs(ll x){
	a[x]=x;
	for(ll i:v[x]){
		dist[i]=dist[x]+1;
		dfs(i);
		a[x]=min(a[x],a[i]);
	}
}
bool cmp(ll x,ll y){
	return a[x]<a[y];
}
void dfs1(ll x){
	for(ll i:v[x]){
		dfs1(i);
	}
	p[x]=u.size();
	u.push_back(x);
}
ll up(ll x){
	ll i;
	for(i=20;i>=0;i--){
		if(ball[jump[x][i]]) x=jump[x][i];
	}
	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];
		s.insert(i-1);
		if(jump[i][0]==0) root=i;
		else v[jump[i][0]].push_back(i);
	}
	for(j=1;j<=20;j++){
		for(i=1;i<=n;i++){
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}
	dfs(root);
	for(i=1;i<=n;i++){
		sort(v[i].begin(),v[i].end(),cmp);
	}
	dfs1(root);
	while(q--){
		cin >> x >> y;
		if(x==1){
			for(i=1;i<=y;i++){
				it=s.begin();
				x=u[*it];
				ball[x]=1;
				s.erase(it);
			}
			cout << x << "\n";
		}
		else{
			x=up(y);
			ball[x]=0;
			s.insert(p[x]);
			cout << dist[y]-dist[x] << "\n";
		}
	}
}

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