Submission #19541652


Source Code Expand

Copy
//#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

Submission Time
Task F - Christmas Tree
User kshitij_789
Language C++ (GCC 9.2.1)
Score 900
Code Size 2856 Byte
Status AC
Exec Time 256 ms
Memory 18624 KB

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

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 75
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 204 ms 9528 KB
02.txt AC 207 ms 9516 KB
03.txt AC 207 ms 9456 KB
04.txt AC 211 ms 9428 KB
05.txt AC 233 ms 17188 KB
06.txt AC 218 ms 18624 KB
07.txt AC 216 ms 12516 KB
08.txt AC 225 ms 14492 KB
09.txt AC 217 ms 13088 KB
10.txt AC 215 ms 14916 KB
11.txt AC 113 ms 9960 KB
12.txt AC 109 ms 9904 KB
13.txt AC 117 ms 9932 KB
14.txt AC 109 ms 9984 KB
15.txt AC 211 ms 9476 KB
16.txt AC 208 ms 9556 KB
17.txt AC 223 ms 9448 KB
18.txt AC 219 ms 9504 KB
19.txt AC 202 ms 9396 KB
20.txt AC 197 ms 9492 KB
21.txt AC 194 ms 9776 KB
22.txt AC 199 ms 10376 KB
23.txt AC 223 ms 17128 KB
24.txt AC 207 ms 16480 KB
25.txt AC 213 ms 9532 KB
26.txt AC 194 ms 9508 KB
27.txt AC 223 ms 9480 KB
28.txt AC 220 ms 9508 KB
29.txt AC 211 ms 9496 KB
30.txt AC 206 ms 9504 KB
31.txt AC 205 ms 9696 KB
32.txt AC 207 ms 10572 KB
33.txt AC 206 ms 16964 KB
34.txt AC 218 ms 15712 KB
35.txt AC 212 ms 9528 KB
36.txt AC 158 ms 9536 KB
37.txt AC 202 ms 9416 KB
38.txt AC 218 ms 9452 KB
39.txt AC 206 ms 9464 KB
40.txt AC 202 ms 9540 KB
41.txt AC 204 ms 9696 KB
42.txt AC 209 ms 10868 KB
43.txt AC 211 ms 13752 KB
44.txt AC 205 ms 13560 KB
45.txt AC 211 ms 9528 KB
46.txt AC 202 ms 9432 KB
47.txt AC 202 ms 9508 KB
48.txt AC 221 ms 9496 KB
49.txt AC 204 ms 9532 KB
50.txt AC 207 ms 9440 KB
51.txt AC 208 ms 9792 KB
52.txt AC 200 ms 10192 KB
53.txt AC 213 ms 12700 KB
54.txt AC 216 ms 15100 KB
55.txt AC 95 ms 11128 KB
56.txt AC 145 ms 11088 KB
57.txt AC 144 ms 11064 KB
58.txt AC 142 ms 11076 KB
59.txt AC 253 ms 12352 KB
60.txt AC 256 ms 11680 KB
61.txt AC 249 ms 11980 KB
62.txt AC 252 ms 12360 KB
63.txt AC 253 ms 12968 KB
64.txt AC 153 ms 14044 KB
65.txt AC 177 ms 14056 KB
66.txt AC 182 ms 13452 KB
67.txt AC 5 ms 5928 KB
68.txt AC 5 ms 5924 KB
69.txt AC 6 ms 5868 KB
70.txt AC 4 ms 5824 KB
71.txt AC 8 ms 5848 KB
72.txt AC 6 ms 5912 KB
s1.txt AC 4 ms 5932 KB
s2.txt AC 5 ms 5800 KB
s3.txt AC 6 ms 5916 KB