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 logos_mhr at 2015-08-20 09:29:16 on Problem 3107
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;
struct point{
	int n;
	point* next;
	void init(int nn){
		n=nn;
		next=NULL;
	}
}*p;
struct link{
	point *head,*last;
	void init(){
		head=new point;
		head->init(0);
		last=head;
	}
	void push(point *p){
		last->next=p;
		last=p;
	}
}l[50010];
int n,s,t,b[50010],son[50010],i,mn=2147483647;
bool vd[50010];
void DFS(int x){
	vd[x]=true;
	son[x]=0;
	b[x]=0;
	int u;
	point *p=l[x].head->next;
	while (p){
		u=p->n;
		if (vd[u]) {
			p=p->next;
			continue;
		}
		DFS(u);
		son[x]+=son[u]+1;
		b[x]=max(b[x],son[u]+1);
		p=p->next;
	}
	b[x]=max(b[x],n-son[x]-1);
	mn=min(mn,b[x]);
}
int main(){
	srand(time(0));
	scanf("%d",&n);
	for(i=1;i<=n;i++) l[i].init();
	for(i=1;i<n;i++) {
		scanf("%d%d",&s,&t);
		p=new point;
		p->init(t);
		l[s].push(p);
		p=new point;
		p->init(s);
		l[t].push(p);
	}
	DFS(rand()%n+1);
	for(i=1;i<=n;i++)
		if (mn==b[i]){
			printf("%d ",i);
		}
}

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