Submission #318551

#	Time	Username	Problem	Language	Result	Execution time	Memory
318551		Gurban	Shymbulak (IZhO14_shymbulak)	C++17	0 / 100	201 ms	19288 KiB

shymbulak

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn=2e5+5;
int n,x,y,vis[maxn],par[maxn],now,sz,L[4*maxn],pos,apos;
ll jog[maxn];
pair<int,int>dp[maxn],T[4*maxn],nw;
vector<int>E[maxn],v;

void dfs(int nd,int pr){
	par[nd] = pr;
	vis[nd] = 1;
	for(auto i : E[nd]){
		if(vis[i] == 1 and i != pr and (int)v.size() == 0){
			now = nd; while(now != i) v.push_back(now),now=par[now]; v.push_back(i);
			continue;
		}
		if(i != pr and vis[i] != 1) dfs(i,nd);
	}
	return;
}

void dfs1(int nd,int pr){
	dp[nd] = {0,1};
	vector<pair<int,int>>res;
	map<int,int>m,p;
	for(auto i : E[nd]){
		if(i != pr and vis[i] == 0){
			dfs1(i,nd);
			res.push_back(dp[i]);
			m[dp[i].first] += dp[i].second;
			p[dp[i].first]++;
		}
	}
	if((int)res.size()==0) return;
	jog[(*m.rbegin()).first+1] += (*m.rbegin()).second;
	if(res.size() > 1){
		sort(res.begin(),res.end());
		if(p[res.back().first] > 1){
			ll jg = 1;
			for(int i = (int)res.size()-1;i >= 0;i--){
				if(res[i].first != res.back().first) break;
				jg *= res[i].second;
			}
			jog[res.back().first*2+2] += jg;
		}
		else {
			auto t = m.rbegin(); t++;
			jog[(*t).first+(*m.rbegin()).first+2] += 1ll * (*t).second * (*m.rbegin()).second;
		}
	}
	dp[nd] = {(*m.rbegin()).first+1,(*m.rbegin()).second};
}

void prop(int nd){
	T[nd*2].first += L[nd];
	L[nd*2] += L[nd];
	T[nd*2+1].first += L[nd];
	L[nd*2+1] += L[nd];
	L[nd] = 0;
}

void f(int nd){
	if(T[nd*2].first == T[nd*2+1].first) T[nd] = {T[nd*2].first,T[nd*2].second+T[nd*2+1].second};
	else if(T[nd*2].first > T[nd*2+1].first) T[nd] = T[nd*2];
	else T[nd] = T[nd*2+1];
}

void upd(int pos,int val,int val1,int l,int r,int nd){
	if(l == r){
		T[nd].first=val,T[nd].second=val1;
		return;
	}
	prop(nd);
	if(pos <= (l+r)/2) upd(pos,val,val1,l,(l+r)/2,nd*2);
	else upd(pos,val,val1,(l+r)/2+1,r,nd*2+1);
	f(nd);
}

void lupd(int a,int b,int val,int l,int r,int nd){
	if(r < a or l > b) return;
	if(l >= a and r <= b){
		T[nd].first += val;
		L[nd] += val;
		return;
	}
	prop(nd);
	lupd(a,b,val,l,(l+r)/2,nd*2);
	lupd(a,b,val,(l+r)/2+1,r,nd*2+1);
	f(nd);
}

pair<int,int>tap(int a,int b,int l,int r,int nd){
	if(r < a or l > b) return {0,0};
	if(l >= a and r <= b) return T[nd];
	prop(nd);
	pair<int,int>cep=tap(a,b,l,(l+r)/2,nd*2);
	pair<int,int>sag=tap(a,b,(l+r)/2+1,r,nd*2+1);
	if(cep.first == sag.first) return {cep.first,cep.second+sag.second};
	if(cep.first > sag.first) return cep;
	return sag;
}

int dis(int a,int b){
	if(b < a) swap(a,b);
	return min(b-a,a+sz-b);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> x >> y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	dfs(1,0);
	
	memset(vis,0,sizeof(vis));
	for(auto i : v) vis[i] = 1;
	for(auto i : v) dfs1(i,0);

	// for(auto i : v) cout<<i<<' '; cout<<'\n';

	// cout<<dp[5].first<<' '<<dp[5].second<<'\n';

	sz = v.size();
	upd(0,dp[v[0]].first,dp[v[0]].second,0,sz-1,1);
	for(int i = 1;i < sz;i++){
		upd(i,dp[v[i]].first+dis(0,i),dp[v[i]].second,0,sz-1,1);
		if(dis(1,i) < dis(0,i)) pos=i;
		if(dis(1,i) == dis(0,i)-1) apos=i;
	}
	if(sz % 2 == 1) apos=-1;
	// cout<<v[apos]<<'\n';
	nw = tap(1,sz-1,0,sz-1,1);
	// cout<<"0 "<<v[0]<<' '<<nw.first<<' '<<nw.second<<' '<<apos<<'\n';
	jog[nw.first+dp[v[0]].first] += 1ll*nw.second*dp[v[0]].second;
	if(apos != -1 and dis(0,apos)+dp[v[apos]].first == nw.first) jog[nw.first+dp[v[0]].first] += 1ll*dp[v[apos]].second*dp[v[0]].second;
	if(apos != -1) apos++;


	for(int i = 1;i < sz-1;i++){
		if(pos == sz) pos = 0;
		if(apos == sz) apos = 0;
		if(pos < i){
			lupd(i,sz-1,-1,0,sz-1,1);
			lupd(0,pos,-1,0,sz-1,1);
			now = pos+1;
			if(dis(now,i) == dis(now,i-1)) now++;
			lupd(now,i-1,1,0,sz-1,1);
		}
		else {
			lupd(i,pos,-1,0,sz-1,1);
			if(dis(0,i) > dis(0,i-1)) lupd(0,i-1,1,0,sz-1,1);
			else if(dis(0,i) == dis(0,i-1)) lupd(1,i-1,1,0,sz-1,1);
			now = pos+1; 
			if(now < sz and dis(i,now) == dis(i-1,now)) now++;
			if(now < sz) lupd(now,sz-1,1,0,sz-1,1);
		}
		nw = tap(i+1,sz-1,0,sz-1,1);
		// cout<< i <<' '<< v[i] << ' '<< nw.first << ' ' << nw.second<<' '<<v[apos]<<'\n';
		jog[nw.first+dp[v[i]].first] += 1ll*nw.second*dp[v[i]].second;
		if(apos != -1 and dis(i,apos)+dp[v[apos]].first == nw.first and apos > i) jog[nw.first+dp[v[i]].first] += 1ll*dp[v[apos]].second*dp[v[i]].second;
		if(apos != -1) apos++;
		pos++;
		// cout<<jog[3]<<'\n';
	}
	for(int i = n;i >= 1;i--) if(jog[i]) return cout<<jog[i],0;
}

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