oj.uz

Submission #967810

# Submission time Handle Problem Language Result Execution time Memory
967810 2024-04-22T22:14:01 Z amirhoseinfar1385 Hard route (IZhO17_road) C++17
0 / 100
 22 ms 49112 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
int n;
vector<int>adj[maxn];
vector<pair<int,int>>alldp[maxn],ps[maxn],suf[maxn];
long long c2(int a){
	long long ret=a;
	ret=ret*(ret-1)/2;
	return ret;
}

pair<int,int>comp(pair<int,int>a,pair<int,int>b){
	pair<int,int>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(1,ret.second);
	}
	return ret;
}

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

pair<int,int> dfsdown(int u=1,int 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<int,int>ret=make_pair(0,1);
	for(auto x:adj[u]){
		if(x==par){
			continue;
		}
		pair<int,int>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(int ind){
	int sz=alldp[ind].size();
	ps[ind].resize(sz+1);
	suf[ind].resize(sz+1);
	for(int 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]);
		}
	}
	for(int 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<int,int>ft[maxn];

void dfsup(int u=1,int par=-1){
	for(int i=0;i<(int)adj[u].size();i++){
		int 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(int i=1;i<=n;i++){
		preall(i);
	}
	dfsup();	
}

long long cal(int u){
	if((int)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(int 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(int i=1;i<=n;i++){
		mainres=max(mainres,cal(i));
	}
	cout<<mainres<<" ";
	long long ted=0;
	for(int 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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 48988 KB Output is correct
2 Correct 11 ms 48984 KB Output is correct
3 Correct 12 ms 48988 KB Output is correct
4 Correct 11 ms 48988 KB Output is correct
5 Correct 11 ms 48988 KB Output is correct
6 Correct 11 ms 48988 KB Output is correct
7 Correct 11 ms 49084 KB Output is correct
8 Correct 11 ms 49112 KB Output is correct
9 Correct 11 ms 48984 KB Output is correct
10 Incorrect 11 ms 48988 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 48988 KB Output is correct
2 Correct 11 ms 48984 KB Output is correct
3 Correct 12 ms 48988 KB Output is correct
4 Correct 11 ms 48988 KB Output is correct
5 Correct 11 ms 48988 KB Output is correct
6 Correct 11 ms 48988 KB Output is correct
7 Correct 11 ms 49084 KB Output is correct
8 Correct 11 ms 49112 KB Output is correct
9 Correct 11 ms 48984 KB Output is correct
10 Incorrect 11 ms 48988 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 48988 KB Output is correct
2 Correct 11 ms 48984 KB Output is correct
3 Correct 12 ms 48988 KB Output is correct
4 Correct 11 ms 48988 KB Output is correct
5 Correct 11 ms 48988 KB Output is correct
6 Correct 11 ms 48988 KB Output is correct
7 Correct 11 ms 49084 KB Output is correct
8 Correct 11 ms 49112 KB Output is correct
9 Correct 11 ms 48984 KB Output is correct
10 Incorrect 11 ms 48988 KB Output isn't correct
11 Halted 0 ms 0 KB -