Submission #963419

#	Time	Username	Problem	Language	Result	Execution time	Memory
963419		pcc	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	178 ms	27060 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;
vector<int> tree[mxn];
vector<int> eul;
int par[mxn][20],dep[mxn];
int N,Q;
int rt;
int dp[mxn];
int dfn[mxn];
int sm[mxn];
set<int> st;

void dfs(int now){
	sm[now] = now;
	for(int i = 1;i<20;i++)par[now][i] = par[par[now][i-1]][i-1];
	for(auto nxt:tree[now]){
		dep[nxt] = dep[now]+1;
		dfs(nxt);
		sm[now] = min(sm[now],sm[nxt]);
	}
	return;
}
void dfs1(int now){
	sort(tree[now].begin(),tree[now].end(),[](int a,int b){return sm[a]<sm[b];});
	for(auto nxt:tree[now])dfs1(nxt);
	dfn[now] = eul.size();
	eul.push_back(now);
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++){
		int p;
		cin>>p;
		par[i][0] = p;
		tree[p].push_back(i);
		if(!p)rt = i;
	}
	par[rt][0] = rt;
	dfs(rt);
	dfs1(rt);
	for(int i = 0;i<N;i++)st.insert(i);
	int C = 0;
	while(Q--){
		int t,k;
		cin>>t>>k;
		int lst = 0;
		//assert(C == N-st.size());
		if(t == 1){
			C += k;
			while(k--){
				lst = eul[*st.begin()];
				st.erase(*st.begin());
				dp[lst] = 1;
			}
			cout<<lst<<'\n';
		}
		else{
			C--;
			lst = k;
			assert(dp[k]);
			for(int i = 19;i>=0;i--){
				if(dp[par[lst][i]])lst = par[lst][i];
			}
			st.insert(dfn[lst]);
			dp[lst] = 0;
			cout<<dep[k]-dep[lst]<<'\n';
		}
	}
	return 0;
}

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