Submission #967813

#	Time	Username	Problem	Language	Result	Execution time	Memory
967813		amirhoseinfar1385	Hard route (IZhO17_road)	C++17	100 / 100	816 ms	210768 KiB

road

#include<bits/stdc++.h>
using namespace std;
const long long maxn=500000+10;
long long n;
vector<long long>adj[maxn];
vector<pair<long long,long long>>alldp[maxn],ps[maxn],suf[maxn];
long long c2(long long a){
	long long ret=a;
	ret=ret*(ret-1)/2;
	return ret;
}

pair<long long,long long>comp(pair<long long,long long>a,pair<long long,long long>b){
	pair<long long,long long>ret=a;
	if(a.first==b.first){
		a.second+=b.first;
	}else if(b.first>a.first){
		ret=b;
	}
	if(ret.first==0){
		ret.second=max(1ll,ret.second);
	}
	return ret;
}

void vorod(){
	cin>>n;
	for(long long i=0;i<n-1;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

pair<long long,long long> dfsdown(long long u=1,long long par=-1){
	if(par!=-1){
		sort(adj[u].begin(),adj[u].end());
		adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),par));
	}
	pair<long long,long long>ret=make_pair(0,1);
	for(auto x:adj[u]){
		if(x==par){
			continue;
		}
		pair<long long,long long>hey=dfsdown(x,u);
		hey.first++;
		alldp[u].push_back(hey);
		if(hey.first==ret.first){
			ret.second+=hey.second;
		}else{
			ret=max(ret,hey);
		}
	}
	return ret;
}

void preall(long long ind){
	long long sz=alldp[ind].size();
	ps[ind].resize(sz+1);
	suf[ind].resize(sz+1);
	for(long long i=1;i<=sz;i++){
		if(ps[ind][i-1].first==alldp[ind][i].first){
			ps[ind][i].first=alldp[ind][i].first;
			ps[ind][i].second=alldp[ind][i].second+ps[ind][i-1].second;
		}else{
			ps[ind][i]=max(ps[ind][i-1],alldp[ind][i-1]);
		}
	}
	for(long long i=sz-1;i>=0;i--){
		if(suf[ind][i+1].first==alldp[ind][i].first){
			suf[ind][i].first=alldp[ind][i].first;
			suf[ind][i].second=alldp[ind][i].second+suf[ind][i+1].second;
		}else{
			suf[ind][i]=max(suf[ind][i+1],alldp[ind][i]);
		}
	}
}
pair<long long,long long>ft[maxn];

void dfsup(long long u=1,long long par=-1){
	for(long long i=0;i<(long long)adj[u].size();i++){
		long long x=adj[u][i];
	//	cout<<"pas: "<<u<<" "<<i<<" "<<x<<" "<<ps[u][i].first<<" "<<suf[u][i].first<<endl;
		ft[x]=comp(ft[u],comp(ps[u][i],suf[u][i+1]));
		ft[x].first++;
		dfsup(x,u);
	}
	if(par!=-1){
		alldp[u].push_back(ft[u]);
	}
}

void pre(){
	dfsdown();
	for(long long i=1;i<=n;i++){
		preall(i);
	}
	dfsup();	
}

long long cal(long long u){
	if((long long)alldp[u].size()<3){
		return 0;
	}
	sort(alldp[u].rbegin(),alldp[u].rend());
	long long ret=alldp[u][0].first*(alldp[u][1].first+alldp[u][2].first);
	return ret;
}

long long calted(long long u){
	sort(alldp[u].rbegin(),alldp[u].rend());	
//	cout<<"hey: "<<u<<endl;
//	for(auto x:alldp[u]){
//		cout<<x.first<<" "<<x.second<<"\n";
//	}
	long long suma=0,ret=0;
	for(auto x:alldp[u]){
		if(x.first==alldp[u][2].first){
			suma+=x.second;
		}
	}
	if(alldp[u][2].first==alldp[u][1].first){
	//	cout<<"wtf: "<<suma<<" "<<c2(suma)<<endl;
		ret+=c2(suma);
		for(auto x:alldp[u]){
			if(x.first==alldp[u][2].first)
				ret-=c2(x.second);
		}
		return ret;
	}
	ret=suma*alldp[u][1].second;
	return ret;
}

void solve(){
	long long mainres=0;
	for(long long i=1;i<=n;i++){
		mainres=max(mainres,cal(i));
	}
	cout<<mainres<<" ";
	long long ted=0;
	for(long long i=1;i<=n;i++){
		if(cal(i)==mainres&&mainres!=0){
			ted+=calted(i);
		}
	}
	if(mainres==0){
		ted=1;
	}
	cout<<ted<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
}

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