Submission #1128524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128524		Alihan_8	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	144 ms	23708 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

struct SegTree{
	vector <int> T;
	
	int n;
	
	SegTree(int n) : T(n * 4 + 5, -1), n(n) {}
	
	void upd(int v, int l, int r, int p, int x){
		if ( l == r ){
			T[v] = x; 
			return;
		}
		
		int m = (l + r) / 2;
		
		if ( p <= m ) upd(v * 2, l, m, p, x);
		else  upd(v * 2 + 1, m + 1, r, p, x);
		
		T[v] = max(T[v * 2], T[v * 2 + 1]);
	}
	
	void set(int p, int x){ upd(1, 0, n, p, x);  } 
	
	int get(int v, int l, int r, int x){
		if ( l == r ) return l;
		
		int m = (l + r) / 2;
		
		return T[v * 2] > x ? get(v * 2, l, m, x) : get(v * 2 + 1, m + 1, r, x);
	}
	
	int qry(int x){ return get(1, 0, n, x); }
};

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, q; cin >> n >> q;
	
	vector <vector<int>> adj(n);
	
	int root = -1;
	
	for ( int i = 0; i < n; i++ ){
		int p; cin >> p;
		
		if ( p != 0 ) adj[p - 1].push_back(i);
		else root = i;
	}
	
	vector <int> s(n);
	
	auto trav = [&](auto trav, int u) -> void{
		s[u] = u;
		
		for ( auto &v: adj[u] ){
			trav(trav, v);
			
			s[u] = min(s[u], s[v]);
		}
	};
	
	trav(trav, root);
	
	for ( auto &v: adj ){
		sort(v.begin(), v.end(), [&](int &i, int &j){
			return s[i] < s[j];
		});
	}
	
	vector <int> d(n), tin(n), tout(n), p(n * 2), f(n * 2);
	
	int ct = -1;
	
	auto dfs = [&](auto dfs, int u) -> void{
		tin[u] = ++ct; p[tin[u]] = u;
		
		for ( auto &v: adj[u] ){
			d[v] = d[u] + 1;
			
			dfs(dfs, v);
		} 
		
		tout[u] = ++ct; f[tout[u]] = u;
	};
	
	dfs(dfs, root);
	
	set <int> st;
	for ( auto &x: tout ) st.insert(x);
	
	SegTree seg(n * 2);
	
	auto ins = [&](){ assert(!st.empty());
		int t = *st.begin(); st.erase(st.begin());
		
		seg.set(tin[f[t]], t);
			
		return f[t];
	};
	
	auto del = [&](int u){
		int t = seg.qry(tin[u]);
		
		st.insert(tout[p[t]]);
		seg.set(t, -1);
		
		return d[u] - d[p[t]];
	};
	
	while ( q-- ){
		int t, u; cin >> t >> u;
		
		if ( t == 1 ){
			int v = -1;
			
			for ( int i = 1; i <= u; i++ ) v = ins();
			
			cout << v + 1 << '\n';
		} else{
			cout << del(u - 1) << '\n';
		}
	}
}

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