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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

各位大神帮忙看一下为什么 总是MLE啊 谢谢了

Posted by 1910799524 at 2017-09-05 19:00:00 on Problem 1330
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10005;
int tme,n;
int cnt;
int root;
int in[N];
int fa[N][17],deep[N];
struct node
{
	int net;
	int to; 
}e[2*N];
int head[N];
void add (int a,int b)
{
	cnt++;
	e[cnt].to=b;
	e[cnt].net=head[a];
	head[a]=cnt;
}
void dfs(int x,int pre,int step)
{
	fa[x][0]=pre;deep[x]=step;
	for(int i=head[x];i;i=e[i].net)
	{
		int t=e[i].to;
		dfs(t,x,step+1);
	}
}
int lca(int x,int y)
{
	int re;
	if(deep[x]<deep[y]) swap(x,y);
	for(int i=16;i>=0;i--)
	{
		if(deep[fa[x][i]]>=deep[y])
			x=fa[x][i];
	}
	if(x==y) return x;
	for(int i=16;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[x][i];
		}
		else re=fa[x][i];
	} 
	return re;
}
int main()
{
	scanf("%d",&tme);
	while(tme--)
	{
		memset(head,0,sizeof(head));
		memset(fa,0,sizeof(fa));
		memset(in,0,sizeof(in));
		memset(deep,0,sizeof(deep));
		scanf("%d",&n); 
		for(int i=1;i<n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			add(x,y);
			in[y]++;
		} 
		for(int i=1;i<=n;i++)
		{
			if(in[i]==0)
			{
				root=i;
				break;
			}
		}
		dfs(root,root,1);
		for(int j=1;j<=16;j++)
	    {
		for(int i=1;i<=n;i++)
		{
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	    }
		int c,d;
		scanf("%d%d",&c,&d);
		int ans=lca(c,d);
		printf("%d\n",ans);
	}
	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