Submission #19541652

---

Source Code Expand

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
int n;
vector<int> adj[100001];
int dp[100001];
int cur;
int st=1;
vector<int> ss2;
bool check2(int ind){
	vector<int> tt;
	for(int i=0;i<ss2.size();i++){
		if(i!=ind){
			tt.pb(ss2[i]);
		}
	}
	int kk=1;
	if(tt.size()%2==1){
		if(tt.back()+1>cur){
			kk=0;
		}
		tt.pop_back();
	}
	for(int i=0;i<tt.size()/2;i++){
		int su=tt[i];
		su+=tt[tt.size()-i-1];
		if(su+1>cur){
			kk=0;
		}
	}
	return kk;
}
void dfs(int no,int par=-1){
	int x=adj[no].size();
	if(no!=0){
		x--;
	}
	vector<int> ss;
	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no);
			ss.pb(dp[j]);
		}
	}
	if(ss.size()==0){
		dp[no]=1;
	}
	else{
		sort(ss.begin(),ss.end());
		if(ss.size()%2==0){
			int mm=1;
			for(int i=0;i<ss.size()/2;i++){
				if(ss[i]+ss[ss.size()-i-1]+1>cur){
					mm=0;
				}
			}
			if(mm==0 and no==0){
				st=0;
			}
			if(mm==1){
				dp[no]=1;
			}
			else{
				int low=0;
				int high=ss.size()-1;
				ss2=ss;
				while(low<high-1){
					int mid=(low+high)/2;
					if(check2(mid)){
						high=mid;
					} 
					else{
						low=mid;
					}
				}
				if(check2(high)==false){
					st=0;
				}
				else{
					int pp=high;
					if(check2(low)){
						pp=min(pp,low);
					}
				//	cout<<pp<<"::"<<endl;
					dp[no]=ss[pp];
					
					if(no!=0){
						dp[no]+=1;
					}
					if(dp[no]+1>cur){
						st=0;
					}
					
				}

			}
		}
		else{
			int low=0;
			int high=ss.size()-1;
			ss2=ss;
			while(low<high-1){
				int mid=(low+high)/2;
				if(check2(mid)){
					high=mid;
				} 
				else{
					low=mid;
				}
			}
			if(check2(high)==false){
				st=0;
			}
			else{
				int pp=high;
				if(check2(low)){
					pp=min(pp,low);
				}
			//	cout<<no<<",,"<<pp<<":"<<endl;
				dp[no]=ss[pp];
				
				if(no!=0){
					dp[no]+=1;
				}
				if(dp[no]+1>cur){
					st=0;
				}
				
			}
		}
	}
/*	if(cur==4){
		cout<<no<<","<<dp[no]<<endl;
	}
*/

}

bool check(int mid){
	cur=mid;
	st=1;
	dfs(0);
	return st;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n-1;i++){
		int aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	}

	int ans=0;
	for(int i=0;i<n;i++){
		int x=adj[i].size();
		if(i>0){
			x--;
		}
		ans+=x/2;
		if(i==0){
			if(x%2==1){
				ans++;
			}
		}
	}
	int low=1;
	int high=n;
	while(low<high-1){
		int mid=(low+high)/2;
		if(check(mid)){
			high=mid;
		}
		else{
			low=mid;
		}
	}
	int ind=high;
	if(check(low)){
		ind=min(ind,low);
	}
	cout<<ans<<" "<<ind-1<<endl;

	
 
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘bool check2(int)’:
./Main.cpp:18:15: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   18 |  for(int i=0;i<ss2.size();i++){
      |              ~^~~~~~~~~~~
./Main.cpp:30:15: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   30 |  for(int i=0;i<tt.size()/2;i++){
      |              ~^~~~~~~~~~~~
./Main.cpp: In function ‘void dfs(int, int)’:
./Main.cpp:58:17: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   58 |    for(int i=0;i<ss.size()/2;i++){
      |                ~^~~~~~~~~~~~

Judge Result