Submission #1185674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185674		PieArmy	Shymbulak (IZhO14_shymbulak)	C++20	70 / 100	49 ms	15172 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;
	for(int i=1;i<=n;i++){
		if(root[i]){
			v.pb(i);
			cal(i,i);
		}
	}
	int cnt=v.size();
	for(int i=0;i<cnt;i++){
		v.pb(v[i]);
	}
	map<int,ll>mp;
	for(int i=1;i<cnt/2;i++){
		mp[dp[v[i]]+i]+=ways[v[i]];
	}
	for(int i=0;i<cnt;i++){
		mp[dp[v[i+cnt/2]]+i+cnt/2]+=ways[v[i+cnt/2]];
		ll x=(--mp.end())->fr-i+dp[v[i]],y=(--mp.end())->sc*ways[v[i]];
		if(ans<x){
			ans=x;
			num=0;
		}
		if(ans==x){
			num+=y;
		}
		mp[dp[v[i+1]]+i+1]-=ways[v[i+1]];
		if(!mp[dp[v[i+1]]+i+1]){
			mp.erase(dp[v[i+1]]+i+1);
		}
	}
	cout<<num<<endl;
}

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