Submission #715769

#	Time	Username	Problem	Language	Result	Execution time	Memory
715769		lukameladze	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	283 ms	37408 KiB

ballmachine

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
// #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int t,n,a[N], par[N][20], mn[N], idx[N],q,rt,del[N];
vector <int> v[N],vec, ord;
set <int> s;
void dfs(int a, int p) {
	mn[a] = a;
	par[a][0] = p;
	for (int i = 1; i <= 18; i++) {
		if (par[a][i - 1]) par[a][i] = par[par[a][i - 1]][i - 1];
	}
	for (int to : v[a]) {
		if (to == p) continue;
		dfs(to, a);
		mn[a] = min(mn[a], mn[to]);
	}
}
bool cmp(int a, int b) {
	return mn[a] < mn[b];
}
void dfs1(int a, int p) {
	vector <int> vec;
	for (int to : v[a]) {
		if (to == p) continue;
		vec.pb(to);
	}
	sort(vec.begin(),vec.end(), cmp);
	for (int to : vec){
		dfs1(to, a);
	}
	s.insert(a);
	ord.pb(a);
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for (int i = 1; i <= n; i++) {
		int p;
		cin>>p;
		if (p == 0) {
			rt = i; continue;
		}
		v[i].pb(p);
		v[p].pb(i);
	}
	ord.pb(0);
	dfs(rt, 0);
	dfs1(rt, 0);
	for (int i = 1; i <= n; i++) {
		idx[ord[i]] = i;
	}
	while (q--) {
		int ty;
		cin>>ty;
		if (ty == 1) {
			int k, ans = 0; cin>>k;
			while(k--) {
				int x = ord[*s.begin()];
				del[x] = 1;
				ans = x;
				s.erase(s.begin());
			}
			cout<<ans<<"\n";
			continue;
		} 
		int cur, ans = 0, x;
		cin>>x; cur = x;
		for (int i = 18; i >= 0; i--) {
			if (par[cur][i] && del[par[cur][i]]) cur = par[cur][i], ans += (1<<i);
		}
		del[cur] = 0; s.insert(idx[cur]);
		cout<<ans<<"\n";
	}
}

Compilation message (stderr)

ballmachine.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~

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