Submission #967812

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
967812	2024-04-22T22:20:53 Z	amirhoseinfar1385	Hard route (IZhO17_road)	C++17	Compilation error	0 ms	0 KB

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(1,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();
}

Compilation message

road.cpp: In function 'std::pair<long long int, long long int> comp(std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
road.cpp:21:30: error: no matching function for call to 'max(int, long long int&)'
   21 |   ret.second=max(1,ret.second);
      |                              ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from road.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
road.cpp:21:30: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   21 |   ret.second=max(1,ret.second);
      |                              ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from road.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
road.cpp:21:30: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   21 |   ret.second=max(1,ret.second);
      |                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from road.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
road.cpp:21:30: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   21 |   ret.second=max(1,ret.second);
      |                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from road.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
road.cpp:21:30: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   21 |   ret.second=max(1,ret.second);
      |                              ^