/ Randle /

记录详情

Wrong Answer


  
# 状态 耗时 内存占用
#1 Accepted 4ms 744.0 KiB
#2 Accepted 3ms 768.0 KiB
#3 Accepted 5ms 728.0 KiB
#4 Accepted 5ms 2.723 MiB
#5 Accepted 5ms 896.0 KiB
#6 Accepted 4ms 892.0 KiB
#7 Accepted 5ms 2.375 MiB
#8 Wrong Answer 7ms 2.5 MiB
#9 Accepted 13ms 2.625 MiB
#10 Wrong Answer 26ms 2.109 MiB

代码

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    char ch=getchar();
    int x=0;
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}
int n,v[110010],ans=0;
struct edge
{
	int to,nex;
}a[210010];
int point[110010],cnt=0;

inline void add(int x,int y)
{
	a[++cnt].to=y;
	a[cnt].nex=point[x];
	point[x]=cnt;
}
int bfs1(int x)
{
	int q[110010],head=1,tail=0;
	int u;
	memset(v,0,sizeof(v));
	q[++tail]=x,v[x]=1;
	while(head<=tail)
	{
		u=q[head++];
		for(int i=point[u];i;i=a[i].nex)
		{
			if(!v[a[i].to])
			{
				q[++tail]=a[i].to;
				v[a[i].to]=1;
			}
		}
	}
	return q[tail];
}
void bfs2(int x)
{
	int q[110010],head=1,tail=0;
	int u,pre[110010];
	memset(v,0,sizeof(v));
	q[++tail]=x,v[x]=1,pre[x]=0;
	while(head<=tail)
	{
		u=q[head++];
		for(int i=point[u];i;i=a[i].nex)
		{
			if(!v[a[i].to])
			{
				pre[a[i].to]=u;
				q[++tail]=a[i].to;
				v[a[i].to]=1;
			}
		}
	}
	memset(v,-1,sizeof(v));
	for(u=q[tail];u;u=pre[u])
		v[u]=0;
}
void dfs(int x)
{
	for(int i=point[x];i;i=a[i].nex)
	{
		if(v[a[i].to]==-1)
		{
			v[a[i].to]=v[x]+1;
			ans=max(ans,v[a[i].to]);
			dfs(a[i].to);
		}
	}
}
int main()
{
	int i,j,k;
	n=read();
	for(i=1;i<n;i++)
	{
		j=read(),k=read();
		add(j,k);
		add(k,j);
	}
	bfs2(bfs1(1));
	for(i=1;i<=n;i++)
		if(v[i]==0)
			dfs(i);
	cout<<ans;
}

信息

递交者
类型
递交
题目
树T1
题目数据
下载
语言
C++
递交时间
2017-11-02 17:35:31
评测时间
2017-11-02 17:35:31
评测机
分数
8
总耗时
82ms
峰值内存
2.723 MiB