Submission #418026

#	Time	Username	Problem	Language	Result	Execution time	Memory
418026		Blagojce	Ball Machine (BOI13_ballmachine)	C++11	100 / 100	665 ms	33932 KiB

ballmachine

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
 
mt19937 _rand(time(NULL));
const int mxn = 1e5+5;
 
 
vector<int> g[mxn];
 
int n, q;
int dep[mxn];

int sparse[mxn][20];
int mi[mxn][20];

int sub[mxn];
int msub[mxn];

int t_p = 1;
int eul[mxn];
int ieul[mxn];


void dfs(int u, int p){
	
	
	ieul[t_p] = u;
	eul[u] = t_p++;
	
	sparse[u][0] = p;
	fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];

	mi[u][0] = min(u, p);
	fr(i, 1, 20){
		mi[u][i] = min(mi[u][i-1], mi[sparse[u][i-1]][i-1]);
	}
	
	msub[u] = u;
	sub[u] = 1;
	for(auto e : g[u]){
		dep[e] = dep[u]+1;
		dfs(e, u);
		msub[u] = min(msub[u], msub[e]);
		sub[u] += sub[e];
	}
}
int A, B;
int lca(int a, int b){
	int d = min(dep[a], dep[b]);
	
	for(int i = 19; i >= 0; i --){
		if(dep[a] - (1<<i) >= d){
			a = sparse[a][i];
		}
		if(dep[b] - (1<<i) >= d){
			b = sparse[b][i];
		}
	}

	
	if(a == b) return a;
	for(int i = 19; i >= 0; i --){
		if(sparse[a][i] != sparse[b][i]){
			a = sparse[a][i];
			b = sparse[b][i];
		}
	}
	A = a;
	B = b;
	return sparse[a][0];
}

int path(int u, int p){
	int ret = n;
	
	
	for(int i = 19; i >= 0; i--){
		if(dep[u] - (1<<i) > dep[p]){
			ret = min(ret, mi[u][i]);
			u = sparse[u][i];
		}
	}
	
	
	return ret;
}

bool cmp(int a, int b){
	int c = lca(a, b);
	
	if(b == c) return true;
	else if(a == c) return false;
	else{
		return msub[A] < msub[B];
		/*int m1 = min(path(a, c), msub[a]);
		int m2 = min(path(b, c), msub[b]);
		return m1 < m2;*/
	}

}

vector<int> v;

int bit[mxn];
void update(int k, int v){
	while(k <= n){
		bit[k] += v;
		k += k&-k;
	}
}

int findpos(){
	int k = 0;
	int sum = 0;
	
	for(int i = 19; i >= 0; i --){
		if(k + (1<<i) <= n && sum + bit[k+(1<<i)] == k+(1<<i)){
			k += (1<<i);
			sum += bit[k];
		}
	}
	return k + 1;
}
int pos[mxn];

int bit2[mxn];


void update2(int k, int v){
	while(k <= n){
		bit2[k] += v;
		k += k&-k;
	}
}
int sum(int k){
	int ret = 0;
	while(k > 0){
		ret += bit2[k];
		k -= k&-k;
	}
	return ret;
}


	int link[mxn];

bool active[mxn];
void solve(){
	cin >> n >> q;
	int r = 0;
	
	fr(i, 0, n){
		int x;
		cin >> x;
		if(x == 0){
			r = i;
			continue;
		}
		link[i] = x-1;
		g[x-1].pb(i);
	}
	
	dfs(r, r);
	fr(i, 0, n) v.pb(i);
	sort(all(v), cmp);
	fr(i, 0, n) pos[v[i]] = i+1;
	
	

	
	fr(i, 0, q){
		char t;
		int x;
		cin >> t >> x;
		if(t == '1'){
			
			int o;
			fr(i, 0, x){
				int p = findpos();
				
				update(p, +1);
				
				int node = v[p-1];
				active[node] = true;
				
				
				update2(eul[node], +1);
				update2(eul[node] + sub[node], -1);
				
				o = p;
			}
			cout<<v[o-1]+1<<endl;
		}
		else{
			--x;
			/*int ans = 0;
			int D = sum(eul[x]);
			while(x != r && active[link[x]]){
				x = link[x];
				++ans;
			}
			cout<<ans<<' '<<D-1<<endl;
			
			
			
			
			
			update(pos[x], -1);
			update2(eul[x], -1);
			update2(eul[x]+sub[x], +1);
			active[x] = false;
			*/
			
			
			
			int D = sum(eul[x]);
			
			cout<<D-1<<endl;
			--D;
			for(int i = 19; i >= 0; i--){
				if(D- (1<<i) >= 0){
					x = sparse[x][i];
					D -= (1<<i);
				}
			}
			
			update(pos[x], -1);
			update2(eul[x], -1);
			update2(eul[x]+sub[x], +1);
		}
		
	}
}
int main(){
	//freopen("ballmachine.g01-1.in", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
}

Compilation message (stderr)

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:207:13: warning: 'o' may be used uninitialized in this function [-Wmaybe-uninitialized]
  207 |    cout<<v[o-1]+1<<endl;
      |            ~^~

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