oj.uz

답안 #26386

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26386 2017-06-29T15:39:10 Z samir_droubi Ball Machine (BOI13_ballmachine) C++14
89.3895 / 100
 723 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);
	}
	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;
	}
	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);
 	if(ord.size()!=n+2)return 1;
	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 main()':
ballmachine.cpp:129:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ord.size()!=n+2)return 1;
                ^
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 17648 KB Output is correct
2 Correct 179 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 36 ms 18176 KB Output is correct
11 Correct 176 ms 19524 KB Output is correct
12 Correct 153 ms 19524 KB Output is correct
13 Incorrect 156 ms 19524 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 19460 KB Output is correct
2 Correct 449 ms 23448 KB Output is correct
3 Correct 199 ms 20056 KB Output is correct
4 Correct 196 ms 19384 KB Output is correct
5 Correct 323 ms 19252 KB Output is correct
6 Incorrect 269 ms 19252 KB Output isn't correct
7 Correct 263 ms 18768 KB Output is correct
8 Correct 196 ms 19460 KB Output is correct
9 Correct 476 ms 23872 KB Output is correct
10 Correct 603 ms 23448 KB Output is correct
11 Incorrect 576 ms 23452 KB Output isn't correct
12 Correct 546 ms 21812 KB Output is correct
13 Correct 406 ms 26652 KB Output is correct
14 Correct 266 ms 20056 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 226 ms 20736 KB Output is correct
2 Correct 723 ms 21888 KB Output is correct
3 Correct 439 ms 25876 KB Output is correct
4 Correct 359 ms 22772 KB Output is correct
5 Correct 349 ms 22440 KB Output is correct
6 Correct 433 ms 22444 KB Output is correct
7 Correct 383 ms 21196 KB Output is correct
8 Correct 426 ms 25876 KB Output is correct
9 Correct 449 ms 23872 KB Output is correct
10 Correct 596 ms 23456 KB Output is correct
11 Correct 606 ms 23456 KB Output is correct
12 Correct 533 ms 21884 KB Output is correct
13 Correct 719 ms 27748 KB Output is correct
14 Correct 249 ms 20060 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 459 ms 23864 KB Output is correct
2 Correct 539 ms 21892 KB Output is correct
3 Correct 333 ms 27752 KB Output is correct
4 Correct 549 ms 23864 KB Output is correct
5 Correct 646 ms 23460 KB Output is correct
6 Incorrect 609 ms 23456 KB Output isn't correct
7 Correct 596 ms 21888 KB Output is correct
8 Correct 406 ms 27748 KB Output is correct
9 Correct 223 ms 20060 KB Output is correct