Submission #1278682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278682		PlayVoltz	Ball Machine (BOI13_ballmachine)	C++20	0 / 100	1099 ms	32732 KiB

ballmachine

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
using namespace std;
 
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int counter=-1;
vector<int> mn, out, depth;
vector<vector<int> > graph, twok;

bool custom(int a, int b){
	return mn[a]<mn[b];
}

void dfs(int node){
	mn[node]=node;
	for (auto num:graph[node])dfs(num), mn[node]=min(mn[node], mn[num]);
	sort(graph[node].begin(), graph[node].end(), custom);
}

void dfs2(int node, int p, int d){
	twok[node][0]=p;
	depth[node]=d;
	for (int i=1; i<20; ++i)twok[node][i]=twok[twok[node][i-1]][i-1];
	for (auto num:graph[node])dfs2(num, node, d+1);
	out[node]=++counter;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q, a, t, root;
	cin>>n>>q>>a;
	graph.resize(n+1);
	out.resize(n+1);
	mn.resize(n+1);
	depth.resize(n+1);
	twok.resize(n+1, vector<int>(20));
	for (int i=1; i<=n; ++i){
		cin>>a;
		if (a)graph[a].pb(i);
		else root=i;
	}
	dfs(root);
	dfs2(root, root, 0);
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	vector<bool> taken(n+1, 0);
	for (int i=1; i<=n; ++i)pq.push(mp(out[i], i));
	while (q--){
		cin>>t>>a;
		if (t==1){
			int ans;
			while (a--)taken[pq.top().se]=1, ans=pq.top().se, pq.pop();
			cout<<ans<<"\n";
		}
		else{
			int ori=a;
			for (int i=19; i>=0; --i)if (taken[twok[a][i]])a=twok[a][i];
			pq.push(mp(out[a], a));
			taken[a]=0;
			cout<<depth[ori]-depth[a]<<"\n";
		}
	}
}

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