Submission #376946

#	Time	Username	Problem	Language	Result	Execution time	Memory
376946		kshitij_sodani	Hard route (IZhO17_road)	C++14	100 / 100	1035 ms	106476 KiB

road

//#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'
llo n;
vector<llo> adj[500001];
pair<llo,llo> ma[5000001];
pair<llo,llo> ma3[5000001];

llo par[5000001];
pair<llo,llo> remax(pair<llo,llo> aa,pair<llo,llo> bb){
	if(bb.a>aa.a){
		return bb;
	}
	if(aa.a==bb.a){
		aa.b+=bb.b;
		return aa;
	}
	return aa;
}
void dfs(llo no,llo par2=-1){
	par[no]=par2;
	ma[no]={0,1};
	for(auto j:adj[no]){
		if(j!=par2){
			dfs(j,no);
			ma[no]=remax(ma[no],{ma[j].a+1,ma[j].b});
		}
	}
}
void dfs2(llo no,llo par2=-1,pair<llo,llo> ma2={0,1}){

	ma3[no]=ma2;
	//cout<<no<<","<<ma2.a<<","<<ma2.b<<endl;
	vector<pair<llo,llo>> xx;
	xx.pb({ma2.a+1,ma2.b});
	for(auto j:adj[no]){
		if(j!=par2){
			xx.pb({ma[j].a+2,ma[j].b});
		}	
	}
	if(par2!=-1){
		if(adj[no].size()==1){
			return;
		}
	}
	sort(xx.begin(),xx.end());
	reverse(xx.begin(),xx.end());
	pair<llo,llo> rr=xx[0];

	for(llo i=1;i<xx.size();i++){
		rr=remax(rr,xx[i]);
	}
	pair<llo,llo> rr2;
	if(xx[0].a!=xx[1].a){
		rr2.a=xx[1].a;
		rr2.b=0;
		for(llo i=1;i<xx.size();i++){
			if(rr2.a==xx[i].a){
				rr2.b+=xx[i].b;
			}
		}
	}

	for(auto j:adj[no]){
		if(j!=par2){
			if(ma[j].a+2==xx[0].a){
				if(ma[j].b==rr.b){
					dfs2(j,no,rr2);
				}
				else{
					dfs2(j,no,{rr.a,rr.b-ma[j].b});
				}
			}
			else{
				dfs2(j,no,rr);
			}
		}
	}

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n-1;i++){
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
		
	}
	llo st=1;
	for(llo i=0;i<n;i++){
		if(adj[i].size()>2){
			st=0;
		}
	}
	if(st){
		cout<<0<<" "<<1<<endl;
		return 0;
	}
	pair<llo,llo> cot={0,0};
	dfs(0);
	dfs2(0);
	for(llo i=0;i<n;i++){
	//	dfs(i);
		vector<pair<llo,llo>> tt;
		for(auto j:adj[i]){
			if(j!=par[i]){
				tt.pb({ma[j].a+1,ma[j].b});
			}
			else{
				tt.pb(ma3[i]);
			}
		}	
		sort(tt.begin(),tt.end());
		reverse(tt.begin(),tt.end());

		if(tt.size()>2){
			if(tt[0].a==tt[1].a and tt[1].a==tt[2].a){
				llo cur=0;
				for(auto j:tt){
					if(j.a==tt[0].a){
						cot=remax(cot,{(2*tt[0].a)*tt[0].a,cur*j.b});
						cur+=j.b;
					}
				}
				continue;
			}
			/*for(auto j:tt){
				cout<<j.a<<","<<j.b<<endl;
			}
			cout<<endl;*/
			if(tt[0].a==tt[1].a){
				llo su=tt[0].a+tt[1].a;
				llo su2=0;
				for(auto j:tt){
					if(j.a==tt[2].a){
						su2+=j.b;
					}
				}
				cot=remax(cot,{tt[0].a*(tt[0].a+tt[2].a),su*su2});
				continue;
			}
			if(tt[1].a==tt[2].a){
				llo cur=0;
				for(auto j:tt){
					if(j.a==tt[1].a){
						cot=remax(cot,{(tt[1].a*2)*tt[0].a,cur*j.b});
						cur+=j.b;
					}
				}
			}
			else{
				llo cur=0;
				for(auto j:tt){
					if(j.a==tt[2].a){
						cot=remax(cot,{(tt[1].a+tt[2].a)*tt[0].a,j.b*tt[1].b});
						//cur+=j.b;
					}
				}	
			}


		}
	}


	cout<<cot.a<<" "<<cot.b<<endl;
	//dfs(0);








 
	return 0;
}

Compilation message (stderr)

road.cpp: In function 'void dfs2(llo, llo, std::pair<long long int, long long int>)':
road.cpp:56:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(llo i=1;i<xx.size();i++){
      |              ~^~~~~~~~~~
road.cpp:63:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(llo i=1;i<xx.size();i++){
      |               ~^~~~~~~~~~
road.cpp: In function 'int main()':
road.cpp:163:9: warning: unused variable 'cur' [-Wunused-variable]
  163 |     llo cur=0;
      |         ^~~

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48