Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这不科学!E[110000][10]就RE,开100就过了……难道有几十个分支?

Posted by liu_cheng_ao at 2016-09-16 23:31:50 on Problem 3321
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<algorithm>

using namespace std;

int E[120000][100],C[120000];
int n,m,a,b,cnt;
int l[120000],r[120000],fa[120000];
int tr[120000];
bool pcked[120000];
int lbt(int a) {return a&(-a);
}
void dfs(int k)
{
	l[k]=++cnt;
	for(int i=1;i<=C[k];i++)
	{
		if(E[k][i]!=fa[k])
		{
			fa[E[k][i]]=k;
			dfs(E[k][i]);
		}
	}
	r[k]=cnt;
}
int s(int x)
{
	int rtn=0;
	while(x>0)
	{
		rtn+=tr[x];
		x-=lbt(x);
	}
	return rtn;
}
void init()
{
	for(int i=1;i<=n;i++)
	tr[i]=lbt(i); 
}
void ad(int x,int d)
{
	while(x<=n)
	{
		tr[x]+=d;
		x+=lbt(x);
	}
}
int main()
{
	scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
    	scanf("%d%d",&a,&b);
    	C[a]++;C[b]++;
    	E[a][C[a]]=b;
    	E[b][C[b]]=a;
    }
    dfs(1);
    init();
    scanf("%d",&m);
    char op[10];int x;
    for(int i=1;i<=m;i++)
    {
    	scanf("%s",&op);
    	scanf("%d",&x);
    	if(op[0]=='Q')
    	printf("%d\n",s(r[x])-s(l[x]-1));
    	else if(op[0]=='C')
    	{
    		if(pcked[x])ad(l[x],1);else ad(l[x],-1);
    		pcked[x]=!pcked[x];
    	}
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator