제출 #1122684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122684		stefanneagu	Ball Machine (BOI13_ballmachine)	C++20	0 / 100	1098 ms	40860 KiB

ballmachine

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int nmax = 1e5 + 5, mod = 1e9 + 1;
 
set<int> s;
vector<int> in[nmax], adj[nmax];
int mps[nmax], v[nmax], to[nmax], back[nmax];
int up[nmax][17], d[nmax];

void dfs1(int i, int tata = 0) {
	mps[i] = v[i];
	for(auto it : in[i]) {
		if(it != tata) {
			dfs1(it, i);
			mps[i] = min(mps[i], mps[it]);
		}
	}
}

int timp = 1;

bool cmp(int a, int b) {
	return mps[a] < mps[b];
}

void dfs2(int i, int tata = 0) {
	for(auto it : in[i]) {
		if(it != tata) {
			dfs2(it, i);
		}
	}
	to[i] = timp;
	back[timp] = i;
	timp++;
}

void dfs(int i, int tata = 0) {
	up[i][0] = tata;
	for(int j = 1; (1 << j) <= d[i]; j++) {
		up[i][j] = up[up[i][j - 1]][j - 1];
	}
	for(auto it : adj[i]) {
		if(it != tata) {
			d[it] = d[i] + 1;
			dfs(it, i);
		}
	}
}

int lift(int a, int nr) {
	for(int i = 0; (1 << i) <= nr; i++) {
		if(nr & (1 << i)) {
			a = up[a][i];
		}
	}
	return a;
}

int qry(int a) {
	int l = 0, r = d[a], ans = 0;
	int nod;
	while(l <= r) {
		int mid = (l + r) / 2;
		nod = lift(a, mid);
		if(s.find(nod) == s.end()) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return ans;
}
	

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	int n, q, root = -1;
	cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		s.insert(i);
		int a;
		cin >> a;
		if(a == 0) {
			root = i;
			continue;
		}
		in[a].push_back(i);
		in[i].push_back(a);
	}
	dfs1(root);
	dfs2(root);
	for(int i = 1; i <= n; i++) {
		for(auto it : in[i]) {
			adj[to[i]].push_back(to[it]);
			adj[to[it]].push_back(to[i]);
		}
	}
	dfs(n);
	while(q--) {
		int t, a;
		cin >> t >> a;
		if(t == 1) {
			int ult = 0;
			while(a--) {
				ult = *s.begin();
				s.erase(ult);
			}
			cout << back[ult] << '\n';
		} else {
			int ans = qry(to[a]);
			cout << " "<<ans << '\n';
			s.insert(lift(to[a], ans));
		}
	}
	return 0;
}

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