Submission #19541638


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==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 0
Code Size 2814 Byte
Status WA
Exec Time 320 ms
Memory 18668 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 0 / 900
Status
AC × 3
AC × 66
WA × 9
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 213 ms 9436 KB
02.txt AC 225 ms 9468 KB
03.txt AC 219 ms 9352 KB
04.txt AC 243 ms 9348 KB
05.txt WA 320 ms 17188 KB
06.txt WA 265 ms 18668 KB
07.txt AC 232 ms 12408 KB
08.txt AC 248 ms 14464 KB
09.txt AC 286 ms 13136 KB
10.txt AC 259 ms 14924 KB
11.txt AC 112 ms 9884 KB
12.txt AC 111 ms 10004 KB
13.txt AC 113 ms 9892 KB
14.txt AC 112 ms 9940 KB
15.txt AC 233 ms 9484 KB
16.txt AC 222 ms 9392 KB
17.txt AC 246 ms 9472 KB
18.txt AC 246 ms 9352 KB
19.txt AC 244 ms 9496 KB
20.txt AC 210 ms 9528 KB
21.txt AC 210 ms 9600 KB
22.txt AC 214 ms 10320 KB
23.txt WA 264 ms 16968 KB
24.txt AC 260 ms 16528 KB
25.txt AC 233 ms 9384 KB
26.txt AC 212 ms 9380 KB
27.txt AC 234 ms 9480 KB
28.txt AC 236 ms 9320 KB
29.txt AC 229 ms 9300 KB
30.txt AC 220 ms 9364 KB
31.txt AC 223 ms 9688 KB
32.txt AC 227 ms 10676 KB
33.txt WA 238 ms 16852 KB
34.txt WA 246 ms 15572 KB
35.txt AC 222 ms 9484 KB
36.txt AC 170 ms 9532 KB
37.txt AC 216 ms 9384 KB
38.txt AC 232 ms 9348 KB
39.txt AC 216 ms 9436 KB
40.txt AC 216 ms 9552 KB
41.txt AC 224 ms 9616 KB
42.txt AC 222 ms 10704 KB
43.txt WA 228 ms 13808 KB
44.txt WA 228 ms 13528 KB
45.txt AC 230 ms 9380 KB
46.txt AC 213 ms 9480 KB
47.txt AC 208 ms 9464 KB
48.txt AC 232 ms 9296 KB
49.txt AC 225 ms 9456 KB
50.txt AC 222 ms 9560 KB
51.txt AC 220 ms 9748 KB
52.txt AC 216 ms 10216 KB
53.txt AC 228 ms 12628 KB
54.txt AC 253 ms 15116 KB
55.txt AC 93 ms 11084 KB
56.txt AC 144 ms 11000 KB
57.txt AC 142 ms 10960 KB
58.txt AC 146 ms 11096 KB
59.txt AC 264 ms 12412 KB
60.txt AC 271 ms 11580 KB
61.txt AC 275 ms 12004 KB
62.txt AC 294 ms 12376 KB
63.txt AC 297 ms 12880 KB
64.txt WA 168 ms 14196 KB
65.txt AC 184 ms 14240 KB
66.txt WA 220 ms 13576 KB
67.txt AC 6 ms 5840 KB
68.txt AC 6 ms 5868 KB
69.txt AC 5 ms 5820 KB
70.txt AC 5 ms 5892 KB
71.txt AC 5 ms 5708 KB
72.txt AC 5 ms 5888 KB
s1.txt AC 5 ms 5824 KB
s2.txt AC 5 ms 5768 KB
s3.txt AC 6 ms 5748 KB