oj.uz

답안 #26372

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26372 2017-06-29T12:15:23 Z samir_droubi Ball Machine (BOI13_ballmachine) C++14
89.3895 / 100
 709 ms 27752 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);
	}
	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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 17648 KB Output is correct
2 Correct 243 ms 19524 KB Output is correct
3 Correct 179 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 3 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 9 ms 17780 KB Output is correct
10 Correct 39 ms 18176 KB Output is correct
11 Correct 279 ms 19524 KB Output is correct
12 Correct 149 ms 19524 KB Output is correct
13 Incorrect 199 ms 19524 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 19460 KB Output is correct
2 Correct 679 ms 23452 KB Output is correct
3 Correct 279 ms 20056 KB Output is correct
4 Correct 283 ms 19388 KB Output is correct
5 Correct 349 ms 19248 KB Output is correct
6 Incorrect 329 ms 19252 KB Output isn't correct
7 Correct 293 ms 18772 KB Output is correct
8 Correct 199 ms 19460 KB Output is correct
9 Correct 533 ms 23876 KB Output is correct
10 Correct 593 ms 23452 KB Output is correct
11 Incorrect 509 ms 23444 KB Output isn't correct
12 Correct 539 ms 21804 KB Output is correct
13 Correct 389 ms 26648 KB Output is correct
14 Correct 249 ms 20056 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 20736 KB Output is correct
2 Correct 709 ms 21888 KB Output is correct
3 Correct 389 ms 25872 KB Output is correct
4 Correct 319 ms 22780 KB Output is correct
5 Correct 333 ms 22440 KB Output is correct
6 Correct 403 ms 22448 KB Output is correct
7 Correct 339 ms 21196 KB Output is correct
8 Correct 413 ms 25872 KB Output is correct
9 Correct 523 ms 23876 KB Output is correct
10 Correct 659 ms 23456 KB Output is correct
11 Correct 676 ms 23456 KB Output is correct
12 Correct 656 ms 21888 KB Output is correct
13 Correct 669 ms 27744 KB Output is correct
14 Correct 243 ms 20060 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 23872 KB Output is correct
2 Correct 569 ms 21888 KB Output is correct
3 Correct 403 ms 27752 KB Output is correct
4 Correct 589 ms 23868 KB Output is correct
5 Correct 683 ms 23456 KB Output is correct
6 Incorrect 596 ms 23456 KB Output isn't correct
7 Correct 636 ms 21888 KB Output is correct
8 Correct 366 ms 27748 KB Output is correct
9 Correct 239 ms 20060 KB Output is correct