Submission #26372

#	Time	Username	Problem	Language	Result	Execution time	Memory
26372		samir_droubi	Ball Machine (BOI13_ballmachine)	C++14	89.39 / 100	709 ms	27752 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
int n,q;
const int mxn=(1e5)+5;
vector<int>tr[mxn];

int dep[mxn];
int pr[mxn][23];

int mn[mxn];
void dfs(int v)
{
	mn[v]=v;
	for(int i=0;i<tr[v].size();++i)
	{
		int u=tr[v][i];
		pr[u][0]=v;
		dep[u]=dep[v]+1;
		dfs(u);
		mn[v]=min(mn[v],mn[u]);
	}
}

int mxlog=0;
void fill()
{
	while((1<<mxlog)<=n)++mxlog;
	for(int j=1;j<mxlog;++j)
		for(int i=1;i<=n;++i)
			pr[i][j]=pr[pr[i][j-1]][j-1];
}

int in[mxn];
vector<int>ord;
bool cmp(int x,int y)
{
	return mn[x]<mn[y];
}
void dfs1(int v)
{
	sort(tr[v].begin(),tr[v].end(),cmp);
	for(int i=0;i<tr[v].size();++i)
	{
		int u=tr[v][i];
		dfs1(u);
	}
	ord.push_back(v);
	in[v]=ord.size()-1;
}

int st[mxn*4];
int lz[mxn*4];
void pros(int p,int l,int r)
{
	if(lz[p]==-1)return;
	st[p]=lz[p]*(r-l+1);
	if(l!=r)
	{
		lz[p*2]=lz[p];
		lz[p*2+1]=lz[p];
	}
	lz[p]=-1;
}
void upd(int p,int l,int r,int i,int j,int x)
{
	pros(p,l,r);
	if(r<i||l>j)return;
	if(l>=i&&r<=j)
	{
		lz[p]=x;
		pros(p,l,r);
		return;
	}
	int md=(l+r)/2;
	upd(p*2,l,md,i,j,x);
	upd(p*2+1,md+1,r,i,j,x);
	st[p]=st[p*2]+st[p*2+1];
}
int sum(int p,int l,int r,int i,int j)
{
	pros(p,l,r);
	if(r<i||l>j)return 0;
	if(l>=i&&r<=j)return st[p];
	int md=(l+r)/2;
	int x=sum(p*2,l,md,i,j);
	int y=sum(p*2+1,md+1,r,i,j);
	return x+y;
}
int bs(int k)
{
	int l=1;
	int r=n;
	while(l<=r)
	{
		int md=(l+r)/2;
		int s=md-sum(1,1,n,1,md);
		if(s<k)l=md+1;
		else if(s>k)r=md-1;
		else return md;
	}
}

int find(int v)
{
	for(int i=mxlog-1;i>=0;--i)
	{
		int p=pr[v][i];
		int vl=0;
		if(p)vl=sum(1,1,n,in[p],in[p]);
		if(vl)v=p;
	}
	return v;
}
int main()
{
	memset(lz,-1,sizeof lz);

	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i)
	{
		int p;
		scanf("%d",&p);
		tr[p].push_back(i);
	}

	ord.push_back(-1);
	dfs(0);
	fill();
	dfs1(0);

	while(q--)
	{
		int ty,x;
		scanf("%d%d",&ty,&x);
		if(ty==1)
		{
			int i=bs(x);
			upd(1,1,n,1,i,1);
			printf("%d\n",ord[i]);
		}
		else
		{
			int v=find(x);
			upd(1,1,n,in[v],in[v],0);
			printf("%d\n",dep[x]-dep[v]);
		}
	}
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tr[v].size();++i)
               ^
ballmachine.cpp: In function 'void dfs1(int)':
ballmachine.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tr[v].size();++i)
               ^
ballmachine.cpp: In function 'int bs(int)':
ballmachine.cpp:101:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:118:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
                     ^
ballmachine.cpp:122:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);
                 ^
ballmachine.cpp:134:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&ty,&x);
                       ^

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