Submission #519570

#	Time	Username	Problem	Language	Result	Execution time	Memory
519570		PoPularPlusPlus	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	283 ms	36204 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

const int N = 100003, L = 25;

vector<int> adj[N];
int tout[N] , timer , cur[N] , up[N][L] , deg[N] , sweepmo[N];

void drymo(int node){
	sweepmo[node] = node;
	for(int i : adj[node]){
		drymo(i);
		sweepmo[node] = min(sweepmo[node] , sweepmo[i]);
	}
}

void dfs(int node , int par){
	up[node][0] = par;
	for(int i = 1; i < L; i++){
		up[node][i] = up[up[node][i-1]][i-1];
	}
	vector<pair<int,int>> v;
	for(int i : adj[node]){
		deg[i] = deg[node] + 1;
		v.pb(mp(sweepmo[i] , i));
	}
	sv(v);
	for(auto i : v){
		dfs(i.vs , node);
	}
	tout[node] = timer++;
}

pair<int,int> find(int node){
	int res = deg[node];
	for(int i = L - 1; i >= 0; i--){
		if(cur[up[node][i]] == 1){
			node = up[node][i];
		}
	}
	return mp(res - deg[node] , node);
}

void solve(){
	int n;
	cin >> n;
	int q;
	cin >> q;
	int root;
	for(int i = 1; i < n + 1; i++){
		int x;
		cin >> x;
		if(x == 0)root = i;
		else adj[x].pb(i);
	}
	drymo(root);
	timer = 0;
	deg[root] = 0;
	dfs(root , root);
	memset(cur,0,sizeof cur);
	set<pair<int,int>> s;
	for(int i = 1; i <= n; i++){
		s.insert(mp(tout[i] , i));
	}
	while(q--){
		int type;
		cin >> type;
		int cnt;
		cin >> cnt;
		if(type == 1){
			int ans;
			while(cnt > 0){
				pair<int,int> p = *s.begin();
				s.erase(s.begin());
				cur[p.vs] = 1;
				ans = p.vs;
				cnt--;
			}
			cout << ans << '\n';
		}
		else {
			pair<int,int> ans = find(cnt);
			cout << ans.vf << '\n';
			cur[ans.vs] = 0;
			s.insert(mp(tout[ans.vs] , ans.vs));
		}
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:93:19: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |    cout << ans << '\n';
      |                   ^~~~
ballmachine.cpp:73:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |  dfs(root , root);
      |  ~~~^~~~~~~~~~~~~

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