oj.uz

Submission #26373

# Submission time Handle Problem Language Result Execution time Memory
26373 2017-06-29T12:31:57 Z samir_droubi Ball Machine (BOI13_ballmachine) C++14
89.3895 / 100
 683 ms 27748 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;
	}
}

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;
	}
	if(v==0)exit(1);
	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

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.2307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17648 KB Output is correct
2 Correct 219 ms 19524 KB Output is correct
3 Correct 196 ms 19524 KB Output is correct
4 Incorrect 0 ms 17648 KB Output isn't correct
5 Correct 0 ms 17648 KB Output is correct
6 Correct 0 ms 17648 KB Output is correct
7 Incorrect 0 ms 17648 KB Output isn't correct
8 Correct 0 ms 17648 KB Output is correct
9 Correct 13 ms 17780 KB Output is correct
10 Correct 46 ms 18176 KB Output is correct
11 Correct 256 ms 19524 KB Output is correct
12 Correct 236 ms 19524 KB Output is correct
13 Incorrect 206 ms 19524 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 19464 KB Output is correct
2 Correct 683 ms 23444 KB Output is correct
3 Correct 259 ms 20056 KB Output is correct
4 Correct 239 ms 19388 KB Output is correct
5 Correct 306 ms 19252 KB Output is correct
6 Incorrect 316 ms 19252 KB Output isn't correct
7 Correct 279 ms 18768 KB Output is correct
8 Correct 189 ms 19460 KB Output is correct
9 Correct 516 ms 23872 KB Output is correct
10 Correct 636 ms 23448 KB Output is correct
11 Incorrect 543 ms 23448 KB Output isn't correct
12 Correct 523 ms 21812 KB Output is correct
13 Correct 326 ms 26652 KB Output is correct
14 Correct 233 ms 20056 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 20740 KB Output is correct
2 Correct 623 ms 21892 KB Output is correct
3 Correct 389 ms 25872 KB Output is correct
4 Correct 329 ms 22776 KB Output is correct
5 Correct 429 ms 22436 KB Output is correct
6 Correct 369 ms 22448 KB Output is correct
7 Correct 373 ms 21192 KB Output is correct
8 Correct 399 ms 25876 KB Output is correct
9 Correct 469 ms 23872 KB Output is correct
10 Correct 573 ms 23460 KB Output is correct
11 Correct 676 ms 23456 KB Output is correct
12 Correct 656 ms 21888 KB Output is correct
13 Correct 659 ms 27748 KB Output is correct
14 Correct 223 ms 20060 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 23868 KB Output is correct
2 Correct 529 ms 21888 KB Output is correct
3 Correct 353 ms 27748 KB Output is correct
4 Correct 586 ms 23868 KB Output is correct
5 Correct 646 ms 23452 KB Output is correct
6 Incorrect 516 ms 23456 KB Output isn't correct
7 Correct 593 ms 21892 KB Output is correct
8 Correct 356 ms 27748 KB Output is correct
9 Correct 216 ms 20060 KB Output is correct