Submission #376941

#	Time	Username	Problem	Language	Result	Execution time	Memory
376941		kshitij_sodani	Hard route (IZhO17_road)	C++14	52 / 100	2077 ms	67740 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,0}){

	ma3[no]=ma2;

	for(auto j:adj[no]){



	}

}*/
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};
	for(llo i=0;i<n;i++){
		dfs(i);
		vector<pair<llo,llo>> tt;
		for(auto j:adj[i]){
			tt.pb({ma[j].a+1,ma[j].b});
		}	
		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 'int main()':
road.cpp:116:9: warning: unused variable 'cur' [-Wunused-variable]
  116 |     llo cur=0;
      |         ^~~

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