Submission #520409

#	Time	Username	Problem	Language	Result	Execution time	Memory
520409		n00bie_1004	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	230 ms	45184 KiB

ballmachine

#include <bits/stdc++.h>
#define test ll t; cin >> t; while(t--)
typedef long long int ll; 

const ll cons = 1e5 + 5; 

using namespace std;
  
ll lev[cons];
ll mini[cons]; 
vector<ll> adj[cons]; 
ll pos[cons], cur = 0;
ll dp[cons][20], l = 19;
void dfs1(ll v, ll par){
	lev[v] = (par != -1 ? lev[par] + 1 : 0); 
	for(ll i = 1; i <= l; i++){
		if(dp[v][i - 1] == -1)
			dp[v][i] = dp[v][i - 1]; 
		else 
			dp[v][i] = dp[dp[v][i - 1]][i - 1]; 
	}
	mini[v] = v; 
	for(auto u : adj[v]){
		if(u != par){
			dfs1(u, v);
			mini[v] = min(mini[v], mini[u]);  
		}
	}
}
void dfs2(ll v, ll par){
	vector<array<ll, 2>> order; 
	for(auto u : adj[v])
		if(u != par)
			order.push_back({mini[u], u}); 
	sort(order.begin(), order.end()); 
	for(auto [minu, u] : order){
		dfs2(u, v); 
	}
	pos[v] = cur++; 
}
int main(){ 
    ios_base::sync_with_stdio(false); cin.tie(NULL); 
 	ll n, q;
 	cin >> n >> q;
 	vector<ll> par(n); 
 	for(auto &u : par)
 		cin >> u, u--;
 	ll root = -1;  
 	for(ll i = 0; i < n; i++){
 		if(par[i] < 0)
 			root = i; 
 		else {
 			adj[i].push_back(par[i]); 
 			adj[par[i]].push_back(i); 
 		}
 	}
 	for(ll i = 0; i < n; i++)
 		dp[i][0] = par[i];
 	dfs1(root, -1);
 	dfs2(root, -1);  
 	// for(ll i = 0; i < n; i++)
 	// 	cout << pos[i] << " "; 
 	// cout << "\n"; 
 	using pll = array<ll, 2>; 
 	priority_queue<pll, vector<pll>, greater<pll>> pq;
 	for(ll i = 0; i < n; i++)
 		pq.push({pos[i], i}); 
 	vector<ll> check(n, 0); 
 	while(q--){
 		ll t;
 		cin >> t; --t;
 		if(!t){
 			ll k;
 			cin >> k;
 			ll ans = -1; 
 			while(k){
 				pll v = pq.top(); 
 				pq.pop(); 
 				check[v[1]] = 1;
 				ans = v[1];  
 				k--; 
 			}
 			cout << ++ans << "\n"; 
 		}
 		else {
 			ll v;
 			cin >> v; --v;
 			ll old_ = lev[v]; 
 			for(ll i = l; i >= 0; i--)
 				if(dp[v][i] != -1 && check[dp[v][i]])
 					v = dp[v][i]; 
 			ll new_ = lev[v]; 
 			check[v] = 0;
 			pq.push({pos[v], v}); 
 			cout << old_ - new_ << "\n"; 
 		}
 	}
 	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; 
}

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