Submission #1181046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181046		tegshzaya	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	249 ms	52104 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