oj.uz

답안 #26371

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26371 2017-06-29T12:07:13 Z samir_droubi Ball Machine (BOI13_ballmachine) C++14
89.3895 / 100
 699 ms 26580 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][20];

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=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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 16476 KB Output is correct
2 Correct 269 ms 18352 KB Output is correct
3 Correct 203 ms 18352 KB Output is correct
4 Incorrect 3 ms 16476 KB Output isn't correct
5 Correct 0 ms 16476 KB Output is correct
6 Correct 3 ms 16476 KB Output is correct
7 Incorrect 3 ms 16476 KB Output isn't correct
8 Correct 3 ms 16476 KB Output is correct
9 Correct 13 ms 16608 KB Output is correct
10 Correct 36 ms 17004 KB Output is correct
11 Correct 259 ms 18352 KB Output is correct
12 Correct 189 ms 18352 KB Output is correct
13 Incorrect 203 ms 18352 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 193 ms 18288 KB Output is correct
2 Correct 583 ms 22272 KB Output is correct
3 Correct 253 ms 18884 KB Output is correct
4 Correct 246 ms 18216 KB Output is correct
5 Correct 316 ms 18080 KB Output is correct
6 Incorrect 296 ms 18076 KB Output isn't correct
7 Correct 296 ms 17592 KB Output is correct
8 Correct 203 ms 18284 KB Output is correct
9 Correct 516 ms 22700 KB Output is correct
10 Correct 636 ms 22276 KB Output is correct
11 Incorrect 529 ms 22280 KB Output isn't correct
12 Correct 546 ms 20632 KB Output is correct
13 Correct 393 ms 25480 KB Output is correct
14 Correct 263 ms 18884 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 19568 KB Output is correct
2 Correct 699 ms 20716 KB Output is correct
3 Correct 366 ms 24704 KB Output is correct
4 Correct 216 ms 21604 KB Output is correct
5 Correct 339 ms 21268 KB Output is correct
6 Correct 436 ms 21268 KB Output is correct
7 Correct 393 ms 20020 KB Output is correct
8 Correct 316 ms 24704 KB Output is correct
9 Correct 423 ms 22700 KB Output is correct
10 Correct 663 ms 22284 KB Output is correct
11 Correct 656 ms 22284 KB Output is correct
12 Correct 639 ms 20716 KB Output is correct
13 Correct 656 ms 26576 KB Output is correct
14 Correct 269 ms 18888 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 583 ms 22696 KB Output is correct
2 Correct 643 ms 20716 KB Output is correct
3 Correct 363 ms 26576 KB Output is correct
4 Correct 576 ms 22700 KB Output is correct
5 Correct 666 ms 22288 KB Output is correct
6 Incorrect 566 ms 22292 KB Output isn't correct
7 Correct 629 ms 20720 KB Output is correct
8 Correct 373 ms 26580 KB Output is correct
9 Correct 256 ms 18888 KB Output is correct