Submission #337811

#	Time	Username	Problem	Language	Result	Execution time	Memory
337811		Kerim	Shymbulak (IZhO14_shymbulak)	C++17	50 / 100	109 ms	23036 KiB

shymbulak

#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,ll> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
stack<int>st;
vector<int>adj[MAXN],v;
int vis[MAXN];
void dfs1(int nd,int pr){
	if(!v.empty())
		return;
	if(vis[nd]){
		while(!st.empty() and st.top()!=nd)
			v.pb(st.top()),st.pop();
		v.pb(nd);
		return;
	}
	st.push(nd);
	vis[nd]=1;
	tr(it,adj[nd])
		if(*it!=pr)
			dfs1(*it,nd);
	st.pop();
}
PII dp[MAXN],ans;
PII merge(PII x,PII y){
	if(x.ff>y.ff)
		return x;
	if(y.ff>x.ff)
		return y;
	return mp(x.ff,x.ss+y.ss);
}
void dfs(int nd,int pr){
	dp[nd]=mp(0,1LL);
	vector<PII>v;
	tr(it,adj[nd])
		if(*it!=pr and !vis[*it]){
			dfs(*it,nd);
			v.pb(dp[*it]);
			dp[nd]=merge(dp[nd],dp[*it]);
		}
	sort(all(v));
	if(int(v.size())>=2){
		PII b=v[v.size()-2],a=v[v.size()-1];
		PII c=mp(a.ff+b.ff,0LL);
		for(int i=0;i<int(v.size());i++)
			if(v[i].ff==b.ff)
				c.ss+=v[i].ss;
		if(a.ff!=b.ff){
			c.ss*=a.ss;
			ans=merge(ans,c);
		}	
		else{
			c.ss*=c.ss;
			for(int i=0;i<int(v.size());i++)
				if(v[i].ff==b.ff)
					c.ss-=v[i].ss*v[i].ss;
			c.ss/=2;
			ans=merge(ans,c);
		}
	}
	else
		ans=merge(ans,dp[nd]);
	dp[nd].ff++;
}
map<int,ll>a;
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int u,v;cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs1(1,-1);int sz=int(v.size());
	if(sz<3){
		puts("0");
		return 0;	
	}
	memset(vis,0,sizeof vis);
	tr(it,v)
		vis[*it]=1;
	vector<PII>g;
	tr(it,v)
		dfs(*it,-1),g.pb(mp(dp[*it].ff-1,dp[*it].ss));
	/*
	int p=0;
	for(int i=0;i<sz-1;i++){
		while(p<sz and p+p<=sz+i+i)
			a[g[p].ff+p]+=g[p].ss,p++;
		a[g[i].ff+i]-=g[i].ss;
		if(!a[g[i].ff+i])
			a.erase(g[i].ff+i);
		PII tmp=*a.rbegin();
		ans=merge(ans,mp(tmp.ff+g[i].ff-i,g[i].ss*tmp.ss));
	}p=sz-1;a.clear();
	for(int i=sz-1;i>=0;i--){
		while(p+p>=sz+i+i)
			a[g[p].ff+sz-p]+=g[p].ss,p--;	
		if(a.size()){
			PII tmp=*a.rbegin();
			ans=merge(ans,mp(tmp.ff+g[i].ff+i,g[i].ss*tmp.ss));	
		}
	}*/
	for(int i=0;i<sz;i++)
		for(int j=i+1;j<sz;j++){
			if(j-i<=sz-j+i)
				ans=merge(ans,mp(g[i].ff+g[j].ff+j-i,g[i].ss*g[j].ss));
			if(j-i>=sz-j+i)
				ans=merge(ans,mp(g[i].ff+g[j].ff+sz-j+i,g[i].ss*g[j].ss));
		}
	cout<<ans.ss<<endl;
	return 0;
}

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