Submission #536493

#	Time	Username	Problem	Language	Result	Execution time	Memory
536493		new_acc	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	227 ms	33024 KiB

ballmachine

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
vi graf[N];
bitset<N>vis;
int pre[N],dep[N],jump[N][20],pod[N],odw[N],l;
set<int>s;
void dfs(int v,int o){
	jump[v][0]=o;
	for(int i=1;i<=19;i++) jump[v][i]=jump[jump[v][i-1]][i-1];
	dep[v]=dep[o]+1;
	pod[v]=v;
	for(auto u:graf[v]) dfs(u,v),pod[v]=min(pod[v],pod[u]);
}
void dfs2(int v){
	vector<pair<int,int> >curr;
	for(auto u:graf[v]) curr.push_back({pod[u],u});
	sort(curr.begin(),curr.end());
	for(auto u:curr) dfs2(u.se);
	pre[v]=++l,odw[l]=v;
	s.insert(l);
}
int Find(int v){
	for(int i=19;i>=0;i--)
		if(vis[jump[v][i]]) v=jump[v][i];
	return v;
}
void solve(){
	int n,q;
	cin>>n>>q;
	int kk=0;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		if(a==0) kk=i;
		else graf[a].push_back(i);
	}
	dfs(kk,kk),dfs2(kk);
	while(q--){
		int a,b;
		cin>>a>>b;
			if(a==1){
				int last=0;
			for(int j=1;j<=b;j++){
				auto it=s.begin();
				last=odw[*it];
				vis[last]=1;
				s.erase(it);
			}
			cout<<last<<"\n";
		}else{
			int num=Find(b);
			cout<<dep[b]-dep[num]<<"\n";
			vis[num]=0,s.insert(pre[num]);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

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