Submission #39890084

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int max_N=2e5+5;
int End[max_N<<1],Last[max_N],Next[max_N<<1],E=1;
inline void add_edge(int x,int y)
{
	End[++E]=y,Next[E]=Last[x],Last[x]=E;
	End[++E]=x,Next[E]=Last[y],Last[y]=E;
}
int dp[max_N][2],lim;
bool ok;
inline bool cmp(int x,int y)
{
	return dp[x][1]>dp[y][1];
}
inline void upd(int &f,vector<int> v)
{
	sort(v.begin(),v.end(),greater<int>());
	if(v[0]+v[1]<=lim)
		f=min(f,v[0]);
}
inline void upd(int &f,int a,int b,int c)
{
	vector<int> v(3);
	v[0]=a,v[1]=b,v[2]=c;
	upd(f,v);
}
inline void upd(int &f,int a,int b,int c,int d)
{
	vector<int> v(4);
	v[0]=a,v[1]=b,v[2]=c,v[3]=d;
	upd(f,v);
}
void dfs(int x,int fa)
{
	vector<int> son;
	for(int i=Last[x];i;i=Next[i])
	{
		int y=End[i];
		if(y!=fa)
		{
			dfs(y,x);
			if(!ok)
				return;
			son.push_back(y);
		}
	}
	sort(son.begin(),son.end(),cmp);
	son.resize(4);
	int a=son[0],b=son[1],c=son[2],d=son[3];
	dp[x][0]=dp[x][1]=lim+1;
	upd(dp[x][0],min(dp[a][0],dp[a][1]+1),dp[b][1]+1,dp[c][1]+1);
	upd(dp[x][0],dp[a][1]+1,min(dp[b][0],dp[b][1]+1),dp[c][1]+1);
	upd(dp[x][1],min(dp[a][0],dp[a][1]+1),min(dp[b][0],dp[b][1]+1),dp[c][1]+1,dp[d][1]+1);
	upd(dp[x][1],min(dp[a][0],dp[a][1]+1),dp[b][1]+1,min(dp[c][0],dp[c][1]+1),dp[d][1]+1);
	upd(dp[x][1],dp[a][1]+1,min(dp[b][0],dp[b][1]+1),min(dp[c][0],dp[c][1]+1),dp[d][1]+1);
	if(dp[x][0]>lim&&dp[x][1]>lim)
		ok=false;
}
inline bool check(int val)
{
	lim=val-1,ok=true;
	dfs(1,0);
	return ok;
}
int main()
{
	int N;
	scanf("%d",&N);
	for(int i=1;i<=N-1;++i)
	{
		int A,B;
		scanf("%d%d",&A,&B);
		add_edge(A,B);
	}
	dp[0][0]=0,dp[0][1]=-1;
	int l=1,r=N-1,ans=N;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))
			ans=mid,r=mid-1;
		else
			l=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:69:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("%d",&N);
      |  ~~~~~^~~~~~~~~
./Main.cpp:73:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   73 |   scanf("%d%d",&A,&B);
      |   ~~~~~^~~~~~~~~~~~~~

Judge Result