Submission #274645

#	Time	Username	Problem	Language	Result	Execution time	Memory
274645		vivaan_gupta	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	383 ms	38392 KiB

ballmachine

		#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <climits>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define f first
#define s second
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define int ll
#define sz(x) (ll)x.size()
#define all(x) (x.begin(),x.end())
using namespace std;

 
const ll INF = 1e12;
const ll N =(1e5+5); // TODO : change value as per problem
const ll MOD = 1e9+7;
vector<int> adj[N];
int dfs_timer = 1,r;
pll ord[N];
set<pll> se;
int up[N][20];
int mn[N],dep[N];
int what[N];
bool ball[N];
void dfs(int u,int p){
	mn[u] = u;
	for(auto v:adj[u]){
		if(v == p) continue;
		dfs(v,u);
		mn[u] = min(mn[u],mn[v]);
	}
}
void comp(int u,int p){
	up[u][0] = p;
	for(int i =1;i<20;i++){
		up[u][i] = up[up[u][i-1]][i-1];
	}
	for(auto v:adj[u]){
		if(v != p){
			dep[v] = dep[u] + 1;
			comp(v,u);
		}
	}

	ord[u].f = dfs_timer++;
	what[u] = dfs_timer-1;
	ord[u].s = u;
}
void solve(){
	int n,q;
	cin>>n>>q;	
	for(int i =1;i<=n;i++){
		int u;
		cin >> u;
		if(u == 0){
			r = i;
			continue;
		}
		adj[u].pb(i);
		adj[i].pb(u);
	}
	dfs(r,0);
	for(int i =1;i<=n;i++){
			sort(adj[i].begin(), adj[i].end(), [&](const int &a, const int &b) {
		return mn[a] < mn[b];
	});

	}
	// for(int i =1;i<=n;i++){
	// 	cout << "NODE " << i << " -> ";
	// 	for(auto j:adj[i]) cout << j << " ";
	// 	cout<<endl;
	// }
	comp(r,0);
	sort(ord+1,ord+n+1);
	for(int i =1;i<=n;i++){
		se.in(ord[i]);
	}
	// for(auto x:se){
	// 	cout << x.s << " ";
	// }
	// cout << endl;
	while(q--){
		int t,k;
		cin >> t >> k;
		if(t == 1){
			// add k nodes to the root
			int ans;
			while(!se.empty() && k){
				pair<int,int> p = *(se.begin());
				se.erase(p);
				if(ball[p.s] == false){
					ans = p.s;
					ball[p.s] = true;
					k--;
				}
			}
			cout << ans << endl;
		}
		else{
			// remove from node k 
			int u = k;
			for(int i =19;i>=0;i--)
				if(ball[up[u][i]] && up[u][i] != 0)
					u = up[u][i];
			ball[u] = false;
			se.in({what[u],u});
			cout << dep[k] - dep[u] << endl;
		}
	}

}
signed main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
     // freopen(".in","r",stdin);freopen(".out","w",stdout);
    
     ll tt=1;   
     // cin >> tt;
    while(tt--){    
        solve();
    }    
}

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