Submission #74670

#	Time	Username	Problem	Language	Result	Execution time	Memory
74670		kjain_1810	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	430 ms	107828 KiB

ballmachine

//RESET VALUES OF N TO AVOID RTE :/
#include<bits/stdc++.h>
#define ind(a) scanf("%d", &a)
#define inlld(a) scanf("%lld", &a)
#define pb push_back
#define f first
#define s second
#define ind2(a, b) scanf("%d%d", &a, &b)
#define ind3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define inlld2(a, b) scanf("%lld%lld", &a, &b)
#define inlld3(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)

using namespace std;

const int N=1e5+5;
const int MOD=1e9+7;
typedef long long ll;
typedef long double ld;	

int power(int a,int b,int m = MOD){
	if(b == 0) return 1;
	if(b == 1) return a;
	int x = power(a,b/2,m)%m;
	x = (x*x)%m;
	if(b%2) return (x*a)%m;
	return x;
}
ll n, q, mini[N], lcapar[N][30], order[N], arr[N];
ll height[N];
vector<ll>adj[N];
set<pair<ll, ll> >ss[N];
void dfs1(ll u, ll par, ll h)
{
	ll anc=1, i=0; 
	ll here=1e9;
	height[u]=h;
	while(anc<=h)
	{
		if(i==0)
			lcapar[u][i]=par;
		else
			lcapar[u][i]=lcapar[lcapar[u][i-1]][i-1];
		anc*=2;
		i++;
	}
	for(auto v:adj[u])
	{
		if(v==par)
			continue;
		dfs1(v, u, h+1);
		here=min(here, min(mini[v], v));
		ss[u].insert({min(mini[v], v), v});
	}
	mini[u]=here;
}
ll tim=1;
void dfs2(ll u)
{
	for(auto v:ss[u])
		dfs2(v.s);
	order[u]=tim++;
}
set<pair<ll, ll> >finalset;
int main()
{
	ll root;
	inlld2(n, q);
	for(ll a=1; a<=n; a++)
	{
		ll p;
		inlld(p);
		if(!p)
			root=a;
		else
		{
			adj[a].pb(p);
			adj[p].pb(a);
		}
	}
	dfs1(root, 0, 0);
	dfs2(root);
	for(ll a=1; a<=n; a++)
		finalset.insert({order[a], a});
	ll ptr=0;
	while(q--)
	{
		ll type, u;
		inlld2(type, u);
		if(type==1)
		{
			ll cnt=0, ans;
			for(auto it:finalset)
			{
				cnt++;
				arr[it.s]=1;
				ans=it.s;
				finalset.erase(it);
				if(cnt==u)
					break;
			}
			printf("%lld\n", ans);
		}
		else
		{
			ll tosub=height[u];
			ll i=log2(height[u])+1;
			while(i>=0)
			{
				if(arr[lcapar[u][i]]==1)
				{
					u=lcapar[u][i];
				}
				else
					i--; //check if correct
			}
			// printf("%lld ", u);
			if(u==0)
				printf("%lld\n", tosub+1);
			else
				printf("%lld\n", tosub-height[u]);
			arr[max((ll)1, u)]=0;
			finalset.insert({order[u], u});
		}
	}
	return 0;
}
//RESET VALUES OF N TO AVOID RTE :/

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:84:5: warning: unused variable 'ptr' [-Wunused-variable]
  ll ptr=0;
     ^~~
ballmachine.cpp:10:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define inlld2(a, b) scanf("%lld%lld", &a, &b)
                      ~~~~~^~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:67:2: note: in expansion of macro 'inlld2'
  inlld2(n, q);
  ^~~~~~
ballmachine.cpp:4:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define inlld(a) scanf("%lld", &a)
                  ~~~~~^~~~~~~~~~~~
ballmachine.cpp:71:3: note: in expansion of macro 'inlld'
   inlld(p);
   ^~~~~
ballmachine.cpp:10:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define inlld2(a, b) scanf("%lld%lld", &a, &b)
                      ~~~~~^~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:88:3: note: in expansion of macro 'inlld2'
   inlld2(type, u);
   ^~~~~~
ballmachine.cpp:81:6: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs2(root);
  ~~~~^~~~~~

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