Submission #777855

#	Time	Username	Problem	Language	Result	Execution time	Memory
777855		raysh07	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	125 ms	32964 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n, q;
const int N = 1e5 + 69;
int lift[N][19], pr[N], root = -1;
bool occ[N];
int mn[N];
vector <int> adj[N];
int timer = 0;
int dep[N];

void dfs(int u){
	mn[u] = u;
	for (int v : adj[u]){
		dep[v] = dep[u] + 1;
		dfs(v);
		mn[u] = min(mn[u], mn[v]);
	}
}

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

void dfs2(int u){
	for (int v : adj[u]){
		dfs2(v);
	}

	pr[u] = ++timer;
}

void Solve()
{
	cin >> n >> q;

	for (int i = 1; i <= n; i++){
		int x; cin >> x;
		lift[i][0] = x;
		adj[x].push_back(i);
		if (x == 0) root = i;

		mn[i] = INF;
	}

	dfs(root);

	for (int i = 1; i <= n; i++){
		sort(adj[i].begin(), adj[i].end(), comp);
	}

	for (int j = 1; j <= 18; j++){
		for (int i = 1; i <= n; i++){
			lift[i][j] = lift[lift[i][j - 1]][j - 1];
		}
	}

	//todo : find list of priorities and push into multiset
	dfs2(root);
	
	priority_queue <pair<int, int>> pq;
	for (int i = 1; i <= n; i++){
		pq.push({-pr[i], i}); 
	}

	for (int i = 1; i <= q; i++){
		int t, x; cin >> t >> x;

		if (t == 1){
			//choose x highest priorities 
			for (int i = 1; i <= x; i++){
				auto pi = pq.top();
				pq.pop();

				int u = pi.s;
				occ[u] = true;

				if (i == x)
				cout << u << "\n";
			}
		} else {
			//find highest occupied parent of x
			assert(occ[x]);
			int y = x;
			for (int i = 18; i >= 0; i--){
				if (occ[lift[y][i]]){
					y = lift[y][i];
				}
			}

			occ[y] = false;
			cout << dep[x] - dep[y] << "\n";
			pq.push({-pr[y], y});
		}
	}
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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