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

求大牛帮我看看~~~为什么会TLE

Posted by lanseniao at 2009-08-01 10:39:54 on Problem 2492
#include<iostream>
using namespace std;
const int size=3005;
int parent[size],rank[size];
bool found;
int findset(int x,int &h,int &c)
{
	h=0;
	c=-1;
	while(x!=parent[x])
	{
		h++;
		c=x;
		x=parent[x];
	}
	return x;
}
void unionset(int x,int y)
{
	int r1,c1,h1;
	int r2,c2,h2;
	r1=findset(x,h1,c1);
	r2=findset(y,h2,c2);
	if(r1==r2)
	{
		if(h1-h2%2==0)
			found=1;
		return;
	}
	if(h1-h2%2==0)
	{
		if(rank[r1]==rank[r2])
		{
			parent[r2]=r1;
			rank[r1]++;
		}
		else if(rank[r1]>rank[2])
			parent[r2]=r1;
		else parent[r1]=r2;
	}
	else 
	{
		if(rank[r1]>=rank[r2])
		{
			parent[r2]=c1;
			rank[r1]=rank[r2]+2>rank[r1]?rank[r2]+2:rank[r1];
		}
		else
		{
			parent[r1]=c2;
			rank[r2]=rank[r1]+2>rank[r2]?rank[r1]+2:rank[r2];
		}
	}
}
int main()
{
	int t,e;
	while(scanf("%d",&t)==1)
	{
		e=1;
		while(t--)
		{
			int i;
			int x,y;
			int n,m;

			scanf("%d%d",&n,&m);
			for(i=1;i<=n;i++)
			{
				parent[i]=i;
				rank[i]=0;
			}

			found=0;
			for(i=0;i<m;i++)
			{
				scanf("%d%d",&x,&y);
				if(found)
					continue;
				unionset(x,y);
			}
			printf("Scenario #%d:\n",e);
			if(found)
				printf("Suspicious bugs found!\n");
			else printf("No suspicious bugs found!\n");
			if(t)
				printf("\n");
			e++;
		}
	}
	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