Submission #968920

#	Time	Username	Problem	Language	Result	Execution time	Memory
968920		NintsiChkhaidze	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	440 ms	39108 KiB

ballmachine

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define left (h*2),l,(l + r)/2
#define right (h*2+1),(l+r)/2 + 1,r
#define pii pair <int,int>
using namespace std;

const int N = 1e5 + 5;

vector <int> v[N];
int ord[N],mn[N],sub[N];
int pr[N],fix[N],d[25][N],t[4*N],id[N];
int lz[4*N],dep[N];

void predfs(int x,int par){
	mn[x] = x;
	dep[x] = dep[par] + 1;
	d[0][x] = par;
	sub[x] = 1;
	for (int to: v[x]){
		if (to == par) continue;
		predfs(to,x);
		mn[x] = min(mn[x],mn[to]);
		sub[x] += sub[to];
	}
}

void dfs(int x,int par,int l,int r){
	
	vector <pii> vec;
	for (int to: v[x]){
		if (to != par) vec.pb({mn[to],to});
	}
	sort(vec.begin(),vec.end());

	int L = l;
	for (auto [p,to]: vec){
		dfs(to,x,L,L + sub[to] - 1);
		L += sub[to];
	}
	ord[r] = x;
}

void build(int h,int l,int r){
	lz[h] = -1;
	if (l == r){
		t[h] = 0;
		return;
	}
	build(left);
	build(right);
	t[h] = t[h*2] + t[h*2 + 1];
}

void push(int h,int l,int r){
	if (lz[h] == -1) return;
	lz[h*2] = lz[h*2+ 1] = lz[h];

	t[h*2] = ((r + l)/2 - l + 1)*lz[h];
	t[h*2 + 1] = (r - (r + l)/2)*lz[h];
	lz[h] = -1;
}

int findk(int h,int l,int r,int k){
	if (l == r) return l;
	push(h,l,r);
	int lft = (l + r)/2 - l + 1 - t[h*2];
	if (lft >= k) return findk(left,k);
	return findk(right,k - lft);
}

void upd(int h,int l,int r,int L,int R,int vl){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		t[h] = vl * (r - l + 1);
		lz[h] = vl;
		return;
	}

	push(h,l,r);
	upd(left,L,R,vl);
	upd(right,L,R,vl);
	t[h] = t[h*2] + t[h*2 + 1];
}

int get(int h,int l,int r,int idx){
	if (l == r) return t[h];
	push(h,l,r);
	if (idx > (l + r)/2) return get(right,idx);
	return get(left,idx);
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

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

	for (int i = 1; i <= n; i++){
		int p;
		cin>>p;
		if (!p) root=i;
		else {
			pr[i] = p;
			v[p].pb(i);
			v[i].pb(p);
		}
	}

	predfs(root,root);
	dfs(root,root,1,n);

	for (int i = 1; i <= n; i++)
		id[ord[i]] = i;
	build(1,1,n);
	for (int i = 1; i <= 18; i++)
		for (int j = 1; j <= n; j++)
			d[i][j] = d[i - 1][d[i - 1][j]];
		
	while (q--){
		int tp,x;
		cin>>tp>>x;

		if (tp == 1){
			int len = findk(1,1,n,x); // me-x nuli vipovot
			upd(1,1,n,1,len,1);
			cout<<ord[len]<<endl;
			continue;
		}

		int y = x,len = 0;
		for (int i = 18; i >= 0; i--){
			if (dep[y] > (1<<i) && get(1,1,n,id[d[i][y]])) { 
				len += (1<<i);
				y = d[i][y];
			}
		}

		upd(1,1,n,id[y],id[y],0);
		cout<<len<<endl;
	}	
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:114:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |  dfs(root,root,1,n);
      |  ~~~^~~~~~~~~~~~~~~

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