Submission #255613

#	Time	Username	Problem	Language	Result	Execution time	Memory
255613		amoo_safar	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	287 ms	31992 KiB

ballmachine

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 20;

int n, q, rt;
int par[N][Log];
int mn[N];

vector<int> G[N];

void DFS(int u, int p){
	par[u][0] = p;
	mn[u] = u;
	for(int i = 1; i < Log; i++) par[u][i] = par[par[u][i - 1]][i - 1];
	for(auto adj : G[u]){
		DFS(adj, u);
		mn[u] = min(mn[u], mn[adj]);
	}
}

set<int> st;

int mk[N], fn[N], rfn[N], T = 0;
void DFS2(int u){
	sort(all(G[u]), [&](int i, int j){
		return mn[i] < mn[j];
	});
	for(auto adj : G[u]){
		DFS2(adj);
	}
	fn[u] = T ++;
	rfn[fn[u]] = u;
	st.insert(fn[u]);
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	int p;
	for(int i = 1; i <= n; i++){
		cin >> p;
		if(p) G[p].pb(i);
		else rt = i;
	}
	DFS(rt, 0);
	DFS2(rt);

	int ty, v, k, res;
	for(int i = 1; i <= q; i++){
		cin >> ty;
		if(ty == 1){
			cin >> k;
			for(int it = 0; it < k; it++){
				v = rfn[*st.begin()];
				st.erase(st.begin());
				mk[v] = 1;
			}
			cout << v << '\n';
		} else {
			cin >> v;
			res = 0;
			for(int lg = Log - 1; lg >= 0; lg--){
				if(mk[par[v][lg]]) res |= 1 << lg, v = par[v][lg];
			}
			mk[v] = 0;
			st.insert(fn[v]);
			cout << res << '\n';
		}
	}
	return 0;
}

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