Submission #282996

#	Time	Username	Problem	Language	Result	Execution time	Memory
282996		theStaticMind	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	870 ms	38548 KiB

ballmachine

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

vector<int> adj[100005];
vector<int> sub(100005, INF);
int anc[20][100005];
int T[100005];
int d[100005];
int root = 0;
map<int, int> emp;

void init(int x){
	sub[x] = x;
	for(auto y : adj[x]) init(y), sub[x] = min(sub[x], sub[y]);
	sort(all(adj[x]), [&](int x, int y){return sub[x] < sub[y];});
}

void dfs(int x){
	static int time = 1;
	for(auto y : adj[x]){
		d[y] = d[x] + 1;
		dfs(y);
	}
	T[x] = time++;
	emp[T[x]] = x;
}

int add(int k){
	int ret;
	while(k--){
		ret = emp.begin()->second;
		emp.erase(emp.begin());
	}
	return ret;
}

int erase(int x){
	assert(!emp.count(T[x]));

	int y = x;

	for(int d = 19; d >= 0; d--){
		if(!emp.count(T[anc[d][y]])) y = anc[d][y];
	}

	assert(y);

	emp[T[y]] = y;

	return d[x] - d[y]; 

}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, q;
	cin >> n >> q;

	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		adj[x].pb(i);
		anc[0][i] = x;
		if(!x) root = i;
	}

	for(int d = 1; d < 20; d++){
		for(int x = 1; x <= n; x++) anc[d][x] = anc[d - 1][anc[d - 1][x]];
	}
	
	init(root);
	dfs(0);

	while(q--){
		int k, x;
		cin >> k >> x;

		if(k == 1){
			cout << add(x) << "\n";
		}
		else{
			cout << erase(x) << "\n";
		}
	}
}

Compilation message (stderr)

ballmachine.cpp: In function 'long long int add(long long int)':
ballmachine.cpp:42:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |  return ret;
      |         ^~~

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