Submission #1185818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185818		PieArmy	Shymbulak (IZhO14_shymbulak)	C++20	100 / 100	46 ms	15216 KiB

shymbulak

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

int n;
vector<int>komsu[200023];
int ans=0;
ll num=0;
int root[200023],dp[200023];
ll ways[200023];

int cycle(int pos,int las){
	root[pos]=1;
	for(int x:komsu[pos]){
		if(x==las)continue;
		if(root[x])return x;
		int y=cycle(x,pos);
		if(y==-1){
			root[pos]=0;
			return -1;
		}
		if(y){
			if(y==pos)return -1;
			return y;
		}
	}
	root[pos]=0;
	return 0;
}

void cal(int pos,int las){
	ways[pos]=1;
	for(int x:komsu[pos]){
		if(x==las)continue;
		if(root[x])continue;
		cal(x,pos);
		if(dp[x]+1+dp[pos]>ans){
			num=0;
			ans=dp[x]+1+dp[pos];
		}
		if(dp[x]+1+dp[pos]==ans){
			num+=ways[x]*ways[pos];
		}
		if(dp[x]+1>dp[pos]){
			dp[pos]=dp[x]+1;
			ways[pos]=0;
		}
		if(dp[x]+1==dp[pos]){
			ways[pos]+=ways[x];
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;cin>>x>>y;
		komsu[x].pb(y);
		komsu[y].pb(x);
	}
	cycle(1,1);
	vector<int>v;
	int bas=0;
	for(int i=1;i<=n;i++){
		if(root[i]){
			if(!bas)bas=i;
			cal(i,i);
		}
	}
	while(true){
		v.pb(bas);
		int las=bas;
		root[bas]=2;
		for(int x:komsu[bas]){
			if(root[x]==1){
				bas=x;
				break;
			}
		}
		if(las==bas)break;
	}
	int cnt=v.size();
	for(int i=0;i<cnt;i++){
		v.pb(v[i]);
	}
	deque<pair<int,ll>>q;
	function<void(pair<int,ll>)>ekle=[&](pair<int,ll>x)->void{
		while(q.size()&&q.back().fr<x.fr){
			q.pop_back();
		}
		if(q.size()&&q.back().fr==x.fr){
			q.back().sc+=x.sc;
		}
		else{
			q.push_back(x);
		}
	};
	for(int i=1;i<cnt/2;i++){
		ekle({dp[v[i]]+i,ways[v[i]]});
	}
	for(int i=0;i<cnt;i++){
		ekle({dp[v[i+(cnt>>1)]]+i+(cnt>>1),ways[v[i+(cnt>>1)]]});
		ll x=q.front().fr-i+dp[v[i]],y=q.front().sc*ways[v[i]];
		if(ans<x){
			ans=x;
			num=0;
		}
		if(ans==x){
			num+=y;
		}
		if(q.front().fr!=dp[v[i+1]]+i+1){
			continue;
		}
		q.front().sc-=ways[v[i+1]];
		if(q.front().sc==0){
			q.pop_front();
		}
	}
	cout<<num<<endl;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50