oj.uz

Submission #94077

# Submission time Handle Problem Language Result Execution time Memory
94077 2019-01-15T16:14:34 Z gumball Ball Machine (BOI13_ballmachine) C++14
100 / 100
 821 ms 39672 KB 
#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;
	bawah(ee*2);
	if(ST[ee*2]>=cc)return cari(aa,ce,cc,ee*2);
	else cari(ce+1,bb,cc-ST[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

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:91:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6136 KB Output is correct
2 Correct 265 ms 22136 KB Output is correct
3 Correct 104 ms 22392 KB Output is correct
4 Correct 6 ms 6008 KB Output is correct
5 Correct 5 ms 6008 KB Output is correct
6 Correct 7 ms 6264 KB Output is correct
7 Correct 8 ms 6264 KB Output is correct
8 Correct 8 ms 6264 KB Output is correct
9 Correct 17 ms 7032 KB Output is correct
10 Correct 44 ms 9976 KB Output is correct
11 Correct 341 ms 22264 KB Output is correct
12 Correct 109 ms 22336 KB Output is correct
13 Correct 197 ms 22156 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 12632 KB Output is correct
2 Correct 668 ms 35124 KB Output is correct
3 Correct 126 ms 31484 KB Output is correct
4 Correct 244 ms 14776 KB Output is correct
5 Correct 327 ms 14684 KB Output is correct
6 Correct 325 ms 14712 KB Output is correct
7 Correct 327 ms 13688 KB Output is correct
8 Correct 99 ms 12664 KB Output is correct
9 Correct 648 ms 35772 KB Output is correct
10 Correct 748 ms 35216 KB Output is correct
11 Correct 522 ms 35084 KB Output is correct
12 Correct 722 ms 33144 KB Output is correct
13 Correct 227 ms 36216 KB Output is correct
14 Correct 124 ms 31408 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 20856 KB Output is correct
2 Correct 766 ms 33696 KB Output is correct
3 Correct 421 ms 33688 KB Output is correct
4 Correct 342 ms 30612 KB Output is correct
5 Correct 458 ms 30216 KB Output is correct
6 Correct 502 ms 30332 KB Output is correct
7 Correct 458 ms 28936 KB Output is correct
8 Correct 469 ms 33608 KB Output is correct
9 Correct 537 ms 35704 KB Output is correct
10 Correct 816 ms 35448 KB Output is correct
11 Correct 821 ms 35396 KB Output is correct
12 Correct 760 ms 33784 KB Output is correct
13 Correct 782 ms 39672 KB Output is correct
14 Correct 311 ms 31492 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 36080 KB Output is correct
2 Correct 713 ms 33696 KB Output is correct
3 Correct 214 ms 39416 KB Output is correct
4 Correct 584 ms 35816 KB Output is correct
5 Correct 771 ms 35304 KB Output is correct
6 Correct 513 ms 35320 KB Output is correct
7 Correct 752 ms 33756 KB Output is correct
8 Correct 266 ms 39528 KB Output is correct
9 Correct 123 ms 31472 KB Output is correct