oj.uz

Submission #26387

# Submission time Handle Problem Language Result Execution time Memory
26387 2017-06-29T15:55:33 Z samir_droubi Ball Machine (BOI13_ballmachine) C++14
100 / 100
 879 ms 32444 KB 
#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);
	}
	in[v]=ord.size();
	ord.push_back(v);
}
 
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;
	}
}
set<int>emp;

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;
}

void pros(int i)
{
	int ans=0;
	while(!emp.empty())
	{
		set<int>::iterator it=emp.begin();
		if(*it>i)break;
		ans=*it;
		emp.erase(it);
	}
	printf("%d\n",ord[ans]);
}
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);
	}
 	for(int i=1;i<=n;++i)emp.insert(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);
			pros(i);
		}
		else
		{
			int v=find(x);
			upd(1,1,n,in[v],in[v],0);
			emp.insert(in[v]);
			printf("%d\n",dep[x]-dep[v]);
		}
	}
	return 0;
}

Compilation message

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:131: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:135:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);
                 ^
ballmachine.cpp:146: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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17652 KB Output is correct
2 Correct 343 ms 22600 KB Output is correct
3 Correct 246 ms 22600 KB Output is correct
4 Correct 0 ms 17652 KB Output is correct
5 Correct 0 ms 17652 KB Output is correct
6 Correct 0 ms 17784 KB Output is correct
7 Correct 3 ms 17784 KB Output is correct
8 Correct 0 ms 17784 KB Output is correct
9 Correct 9 ms 18048 KB Output is correct
10 Correct 56 ms 18880 KB Output is correct
11 Correct 406 ms 22600 KB Output is correct
12 Correct 203 ms 22600 KB Output is correct
13 Correct 263 ms 22600 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 20300 KB Output is correct
2 Correct 739 ms 28136 KB Output is correct
3 Correct 356 ms 24604 KB Output is correct
4 Correct 303 ms 20852 KB Output is correct
5 Correct 406 ms 20724 KB Output is correct
6 Correct 373 ms 20720 KB Output is correct
7 Correct 356 ms 19996 KB Output is correct
8 Correct 189 ms 20304 KB Output is correct
9 Correct 589 ms 28564 KB Output is correct
10 Correct 729 ms 28136 KB Output is correct
11 Correct 663 ms 28136 KB Output is correct
12 Correct 709 ms 26396 KB Output is correct
13 Correct 336 ms 30792 KB Output is correct
14 Correct 236 ms 24604 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 23080 KB Output is correct
2 Correct 879 ms 26584 KB Output is correct
3 Correct 486 ms 29628 KB Output is correct
4 Correct 369 ms 26528 KB Output is correct
5 Correct 529 ms 26188 KB Output is correct
6 Correct 526 ms 26192 KB Output is correct
7 Correct 506 ms 24948 KB Output is correct
8 Correct 483 ms 29632 KB Output is correct
9 Correct 653 ms 28564 KB Output is correct
10 Correct 753 ms 28148 KB Output is correct
11 Correct 763 ms 28148 KB Output is correct
12 Correct 769 ms 26580 KB Output is correct
13 Correct 609 ms 32444 KB Output is correct
14 Correct 379 ms 24624 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 28560 KB Output is correct
2 Correct 623 ms 26584 KB Output is correct
3 Correct 399 ms 32436 KB Output is correct
4 Correct 649 ms 28564 KB Output is correct
5 Correct 616 ms 28148 KB Output is correct
6 Correct 519 ms 28148 KB Output is correct
7 Correct 639 ms 26580 KB Output is correct
8 Correct 459 ms 32444 KB Output is correct
9 Correct 259 ms 24624 KB Output is correct