Submission #145517

#	Time	Username	Problem	Language	Result	Execution time	Memory
145517		miguel	Ball Machine (BOI13_ballmachine)	C++14	91.43 / 100	1061 ms	33164 KiB

ballmachine

/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░*/
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
const ll mod = 1000000007;
const ll nmax=100010;
#define int ll
int p[100010][18], n, q, root, subtree[100010], id[100010], cnt=1;
vi g[100010];
set<pi> s;

int dfs(int nod){
	int mn=1e9;
	for(int i: g[nod]){
		mn=min(dfs(i), mn);
	}
	subtree[nod]=min(mn, nod);
	return subtree[nod];
}

void dfs_id(int nod){
	for(int i: g[nod]){
		dfs_id(i);
	}
	id[nod]=cnt;
	cnt++;
}

void dfs_p(int nod){
	for(int i=1; i<=17; i++) p[nod][i]=p[p[nod][i-1]][i-1];
	for(int i: g[nod]) dfs_p(i);
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>q;
    for(int i=1; i<=n; i++){
		cin>>p[i][0];
		g[p[i][0]].pb(i);
		if(p[i][0]==0) root=i;
	}
	dfs(root);
	for(int i=1; i<=n; i++){
		if(g[i].size()) sort(g[i].begin(), g[i].end(), [](int a, int b){return (subtree[a]<subtree[b]);});
	}
	//id-s(order) and parents by lifting ye boi
	dfs_id(root);
	s.insert({(ll)1e9, 0LL});
	for(int i=1; i<=n; i++) s.insert({id[i], i});
	dfs_p(root);
	while(q--){
		int op, x;
		cin>>op>>x;
		if(op==1){
			for(int cnt=1; cnt<=x; cnt++){
				if(cnt==x) cout<<(*s.begin()).y<<"\n";
				s.erase(s.begin());
			}
		}
		else if(op==2){
			int cur=x, ans=0;
			for(int i=17; i>=0; i--){
				int nod=p[cur][i]; 
				if(nod!=0 && (s.size()==0 || s.find(make_pair(id[nod], nod))==s.end())) cur=nod, ans+=(nod!=0)*(1<<i);
			}
			cout<<ans<<"\n";
			s.insert({id[cur], cur});
			//for(pi i : s) cout<<i.y<<" "; cout<<endl;
		}
	}
}

Compilation message (stderr)

ballmachine.cpp:22:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")

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