/ Randle /

记录详情

Wrong Answer

/in/foo.cc: In function 'int bfs1(int)':
/in/foo.cc:32:6: warning: unused variable 'd' [-Wunused-variable]
  int d[100010],u;
      ^
/in/foo.cc: In function 'void bfs2(int)':
/in/foo.cc:52:6: warning: unused variable 'd' [-Wunused-variable]
  int d[100010],u,pre[100010];
      ^
# 状态 耗时 内存占用
#1 Accepted 5ms 640.0 KiB
#2 Accepted 5ms 724.0 KiB
#3 Accepted 4ms 768.0 KiB
#4 Accepted 4ms 640.0 KiB
#5 Accepted 4ms 748.0 KiB
#6 Accepted 3ms 728.0 KiB
#7 Accepted 4ms 2.484 MiB
#8 Wrong Answer 6ms 768.0 KiB
#9 Accepted 15ms 1.484 MiB
#10 Wrong Answer 26ms 2.078 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[100010],ans=0;
struct edge
{
	int to,nex;
}a[200010];
int point[100010],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[100010],head=1,tail=0;
	int d[100010],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[100010],head=1,tail=0;
	int d[100010],u,pre[100010];
	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:25:26
评测时间
2017-11-02 17:25:26
评测机
分数
8
总耗时
81ms
峰值内存
2.484 MiB