Submission #94078

#	Time	Username	Problem	Language	Result	Execution time	Memory
94078		gumball	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	823 ms	39784 KiB

ballmachine

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,i,ta,ROOT,p[22][101010],pri[101010],nil[101010],j,te,dep[101010],q,ST[404040],LZ[404040],bes[404040],tb;
vector<ll> v[101010];
ll mi[101010];
bool cmp(ll aa,ll bb)
{
	return (mi[aa]<mi[bb]);
}
void dfs0(ll aa)
{
	mi[aa]=aa;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
	{
		dfs0(v[aa][ii]);
		mi[aa]=min(mi[aa],mi[v[aa][ii]]);
	}
	sort(v[aa].begin(),v[aa].end(),cmp);
}
void dfs(ll aa,ll bb)
{
	dep[aa]=bb;
	mi[aa]=aa;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
		dfs(v[aa][ii],bb+1);
	pri[++te]=aa;
	nil[aa]=te;
}
void bawah(ll ee)
{
	if(LZ[ee]!=-1)
	{
		ST[ee]=LZ[ee]*bes[ee];
		if(bes[ee]>1)
		{
			LZ[ee*2]=LZ[ee];
			LZ[ee*2+1]=LZ[ee];
		}
		LZ[ee]=-1;
	}
}
void upd(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff)
{
	bes[ee]=bb-aa+1;
	bawah(ee);
	if(bb<cc||dd<aa)return ;
	else if(cc<=aa&&bb<=dd)
	{
		ST[ee]=ff*(bb-aa+1);
		if(aa<bb)
		{
			LZ[ee*2]=ff;
			LZ[ee*2+1]=ff;
		}
	}
	else
	{
		ll ce=(aa+bb)/2;
		upd(aa,ce,cc,dd,ee*2,ff);
		upd(ce+1,bb,cc,dd,ee*2+1,ff);
		ST[ee]=ST[ee*2]+ST[ee*2+1];
	}
}
ll que(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	if(cc==0)return 1;
	bawah(ee);
	if(bb<cc||dd<aa)return 0;
	if(cc<=aa&&bb<=dd)return ST[ee];
	else 
	{
		ll ce=(aa+bb)/2;
		return que(aa,ce,cc,dd,ee*2)+que(ce+1,bb,cc,dd,ee*2+1);
	}
}
ll cari(ll aa,ll bb,ll cc,ll ee)
{
	bawah(ee);
	if(aa==bb)return aa; 
	ll ce=(aa+bb)/2;
	if(que(aa,ce,aa,ce,ee*2)>=cc)return cari(aa,ce,cc,ee*2);
	else cari(ce+1,bb,cc-que(aa,ce,aa,ce,ee*2),ee*2+1);
}
int main()
{
	ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>q;
	for(i=1;i<=n;i++)
	{
		cin>>ta;
		if(ta==0)
		{
			ROOT=i;
			p[0][i]=0;
		}
		else
		{
			v[ta].pb(i);
			p[0][i]=ta;
		}
	}
	memset(LZ,-1,sizeof(LZ));
	dfs0(ROOT);
	dfs(ROOT,1);
	for(i=1;i<=20;i++)
		for(j=1;j<=n;j++)
			p[i][j]=p[i-1][p[i-1][j]];
	//for(i=1;i<=n;i++)cout<<i<<" "<<p[1][i]<<"\n";
	for(i=1;i<=n;i++)upd(1,n,i,i,1,1);
	while(q--)
	{
		cin>>ta>>tb;
		if(ta==1)
		{
			ll x=cari(1,n,tb,1);
			//cout<<x<<"\n";
			upd(1,n,1,x,1,0);
			cout<<pri[x]<<"\n";
		}
		else
		{
			//for(i=1;i<=n;i++)cout<<i<<" "<<que(1,n,i,1)<<"\n";
			ll x=0;
			for(i=20;i>=0;i--)
			{
				//cout<<i<<"  "<<tb<<" "<<p[i][tb]<<" \n";
				if(que(1,n,nil[p[i][tb]],nil[p[i][tb]],1)==0)
				{
					x+=(1<<i);
					tb=p[i][tb];
				}
			}
			cout<<x<<"\n";
			upd(1,n,nil[tb],nil[tb],1,1);
		}
	}
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs0(long long int)':
ballmachine.cpp:19:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs(long long int, long long int)':
ballmachine.cpp:31:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'long long int cari(long long int, long long int, long long int, long long int)':
ballmachine.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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