Submission #967329

#	Time	Username	Problem	Language	Result	Execution time	Memory
967329		penguin133	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	334 ms	59728 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n, q;
vector<int>v[200005];
int sub[200005];
deque<int>dq;
priority_queue<int, vector<int>, greater<int> > pq;
void dfs(int x){
	sub[x] = min(sub[x], x);
	for(auto i : v[x]){
		dfs(i);
		sub[x] = min(sub[x], sub[i]);
	}
}
bool cmp(int a, int b){
	return sub[a] < sub[b];
}
void dfs2(int x){
	vector<int>tmp;
	for(auto i : v[x])tmp.push_back(i);
	sort(tmp.begin(), tmp.end(), cmp);
	for(auto i : tmp)dfs2(i);
	if(x)dq.push_back(x);
}
int par[20][200005];
int vis[200005];
void dfs3(int x, int p){
	if(x)par[0][x] = p;
	for(auto i : v[x]){
		dfs3(i, x);
	}
}
int c(int x, int k){
	for(int i=0;i<=19;i++){
		if(k >> i & 1)x = par[i][x];
		if(x == -1)return 0;
	}
	return vis[x];
}
int lnk[200005];
void solve(){
	cin >> n >> q;
	for(int i=1;i<=n;i++){
		int x;cin >> x;
		v[x].push_back(i);
	}
	for(int i=1;i<=n;i++)sub[i] = 1e9;
	dfs(0);
	dfs2(0);
	dfs3(0, -1);
	for(int i=1;i<=19;i++)for(int j=1;j<=n;j++)par[i][j] = par[i-1][par[i-1][j]];
	for(int i=0;i<n;i++)pq.push(i), lnk[dq[i]] = i;
	while(q--){
		int x;cin >> x;
		if(x == 1){
			int k;cin >> k;
			int tmp;
			for(int i=0;i<k;i++){
				tmp = dq[pq.top()];
				pq.pop();
				vis[tmp] = 1;
			}
			cout << tmp << '\n';
		}
		else{
			int k;cin >> k;
			int s = 1, e = n, ans = 0;
			while(s <= e){
				int m = (s + e)/2;
				if(c(k, m))ans = m, s = m + 1;
				else e = m - 1;
			}
			int tmp = k;
			for(int i=0;i<=19;i++)if(ans >> i & 1)tmp = par[i][tmp];
			vis[tmp ] =0;
			pq.push(lnk[tmp]);
			cout << ans << '\n';
		}
	}
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

ballmachine.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main(){
      | ^~~~

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