Submission #116333

#	Time	Username	Problem	Language	Result	Execution time	Memory
116333		ZwariowanyMarcin	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	453 ms	30212 KiB

ballmachine

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


#define pb push_back
#define ld long double
#define fi first
#define se second
#define ll long long
#define ss(x) (int) x.size()
#define mp make_pair
#define FOR(i, n) for(int i = 1; n >= i; ++i)

using namespace std;
using namespace __gnu_pbds;

const int nax = 1e5 + 5, pod = (1 << 19), mod = 998244353;
const ll inf = 1e18;

int n, q;
int root;
vector <int> v[nax];
int black[nax], lca[nax][17];
int dp[nax];
int pr[nax];
int fre = 0;
int liczba[nax];

void dfs(int node) {
	dp[node] = node;
	for(auto it: v[node]) {
		dfs(it);
		dp[node] = min(dp[node], dp[it]);
		lca[it][0] = node;
	}
}

void go(int node) {
	vector <pair<int, int>> e;
	for(auto it: v[node]) {
		e.pb(mp(dp[it], it));
	}
	sort(e.begin(), e.end());
	for(auto it: e) {
		go(it.se);
	}
	pr[node] = fre++;
}

set <pair<int, int>> s;

int add() {
	pair<int, int> x = *s.begin();
	black[x.se] = 1;
	liczba[lca[x.se][0]]++;
	if(liczba[lca[x.se][0]] == ss(v[lca[x.se][0]]))
		s.insert(mp(pr[lca[x.se][0]], lca[x.se][0]));
	s.erase(s.begin());
	return x.se;
}
	


int main() {
	
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		int p;
		cin >> p;
		if(!p)
			root = i;
		else
			v[p].pb(i);
	}
	dfs(root);
	for(int j = 1; j <= 16; ++j)
		for(int i = 1; i <= n; ++i)
			lca[i][j] = lca[lca[i][j - 1]][j - 1];
	go(root);
	
	for(int i = 1; i <= n; ++i) 
		s.insert(mp(pr[i], i));
	while(q--) {
		int type;
		int k;
		cin >> type >> k;
		if(type == 1) {
			int res = -1;
			while(k--) {
				res = add();
			}
			cout << res << endl;
		}
		else {
			int w = k;
			int dis = 0;
			for(int i = 16; 0 <= i; --i) {
				int r = lca[w][i];
				if(!r)
					continue;
				if(black[r]) {
					w = r;
					dis += (1 << i);
				}
			}
			black[w] = 0;
			if(s.find(mp(pr[lca[w][0]], lca[w][0])) != s.end())
				s.erase(mp(pr[lca[w][0]], lca[w][0]));
			liczba[lca[w][0]]--;
			s.insert(mp(pr[w], w));
			cout << dis << endl;
		}
	}
			
			
	
	
	
	
		
	
    return 0;
}

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