Submission #1181045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181045		sodbayr	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	162 ms	52128 KiB

ballmachine

#include<bits/stdc++.h>
#define ll long long
#define ss second
#define ff first
#define pb push_back
#define endl "\n"
using namespace std;
	ll n,q,rr,a[100005];
	set<pair<ll,ll> > s;
	vector<vector<ll> > v,sp;
	vector<ll> m,v1,b,vv;
void rec(ll x,ll y){
	m[x]=x;
	for(auto i : v[x]){
		if(i==y) continue;
		rec(i,x);
		m[x]=min(m[x],m[i]);
	}
}
void res(ll x,ll y){
	vector<pair<ll,ll> > v2;
	for(auto i : v[x]){
		if(i==y) continue;
		v2.pb({m[i], i});
	}
	sort(v2.begin(),v2.end());
	for(ll i=0;i<v2.size();i++){
		res(v2[i].ss,x);
	}
	v1.pb(x);
}
ll rev(ll x){
	ll c=0;
	for(ll i=20;i>=0;i--){
		ll k=sp[x][i];
		if(vv[k]==1){
			x=k;
			c+=(1<<i);
		}
	}
	cout<<c<<endl;
	return x;
}
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;rr=1;
	v.resize(n+1);
	m.resize(n+1);
	sp.resize(n+1,vector<ll> (25));
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		sp[i][0]=a[i];
		if(a[i]==0) rr=i;
		else{
			v[a[i]].pb(i);
			v[i].pb(a[i]);
		}
	}
	rec(rr,0);
	res(rr,0);
	b.resize(n+1);
	vv.resize(n+1,0);
	for(ll i=0;i<v1.size();i++){
		s.insert({i,v1[i]});
		b[v1[i]]=i;
	}
	for(ll j=1;j<=20;j++){
		for(ll i=1;i<=n;i++){
			sp[i][j]=sp[sp[i][j-1]][j-1];
		}
	}
	while(q--){ll k,t,x;
		cin>>t>>x;
		if(t==1){
			while(x--){
				k=(*s.begin()).ss;
				vv[k]=1;
				s.erase(s.begin());
			}
			cout<<k<<endl;
		}
		else{
			k=rev(x);
			vv[k]=0;
			s.insert({b[k],k});
		}
	}
}

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