/ Randle /

记录详情

Wrong Answer


  
# 状态 耗时 内存占用
#1 Accepted 5ms 1.25 MiB
#2 Accepted 7ms 2.746 MiB
#3 Accepted 5ms 2.477 MiB
#4 Accepted 5ms 2.754 MiB
#5 Accepted 4ms 3.223 MiB
#6 Accepted 8ms 3.25 MiB
#7 Accepted 4ms 1.145 MiB
#8 Wrong Answer 6ms 2.625 MiB
#9 Accepted 14ms 3.117 MiB
#10 Wrong Answer 29ms 2.617 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[210010],ans=0;
struct edge
{
	int to,nex;
}a[210010];
int point[210010],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[210010],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[210010],head=1,tail=0;
	int u,pre[210010];
	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;
	return 0;
}

信息

递交者
类型
递交
题目
树T1
题目数据
下载
语言
C++
递交时间
2017-11-03 08:17:55
评测时间
2017-11-03 08:17:55
评测机
分数
8
总耗时
92ms
峰值内存
3.25 MiB