Submission #129094

#	Time	Username	Problem	Language	Result	Execution time	Memory
129094		faustaadp	Shymbulak (IZhO14_shymbulak)	C++17	100 / 100	252 ms	35296 KiB

shymbulak

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,i,ta,tb,p[201010],b[201010],CS,ma,jum,has,j,K;
vector<ll> v[201010],cyc,isi[201010],tom;
pair<ll,ll> A[201010],za[202020];
ll ST[2][1601601];
ll byk[2][1601601];
ll zx[202020];
ll zy[202020];
void dfs(ll aa)
{
	b[aa]=1;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
	{
		if(v[aa][ii]==p[aa]||b[v[aa][ii]]==2)continue;
		if(b[v[aa][ii]])
		{
			ll tem=aa;
			cyc.pb(tem);
			while(tem!=v[aa][ii])
			{
				tem=p[tem];
				cyc.pb(tem);
			}
		}
		else
		{
			p[v[aa][ii]]=aa;
			dfs(v[aa][ii]);
		}
	}
	b[aa]=2;
}
void dfs1(ll aa,ll bb,ll cc)
{
	isi[i].pb(aa);
	if(ma<cc)
	{
		ma=max(ma,cc);
		jum=0;
	}
	if(ma==cc)
		jum++;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
	{
		if(b[v[aa][ii]])continue;
		if(v[aa][ii]==bb)continue;
		dfs1(v[aa][ii],aa,cc+1);
	}
}
void dfs2(ll aa,ll bb)
{
	//cout<<isi[i][j]<<" "<<aa<<" "<<cc<<"_\n";
	ll ii;
	vector<pair<ll,ll> > tim;
	zy[aa]=1;
	zx[aa]=-100;
	for(ii=0;ii<v[aa].size();ii++)
	{
		if(b[v[aa][ii]])continue;
		if(v[aa][ii]==bb)continue;
		dfs2(v[aa][ii],aa);
		if(zx[aa]<zx[v[aa][ii]])
		{
			zx[aa]=max(zx[aa],zx[v[aa][ii]]);
			zy[aa]=0;
			//cout<<aa<<"___\n";
		}
		if(zx[aa]==zx[v[aa][ii]])
		{
			zy[aa]+=zy[v[aa][ii]];
		}
		tim.pb(za[v[aa][ii]]);
	}
	//cout<<aa<<" "<<zy[aa]<<"AA\n";
	if(zx[aa]<0)	
	{
		zx[aa]=0;
 
	}
	zx[aa]++;
	sort(tim.begin(),tim.end());
	reverse(tim.begin(),tim.end());
	ll TS=tim.size();
	if(TS<=1)
	{
		if(ma<(zx[aa]-1))
		{
			ma=max(ma,zx[aa]-1);
			jum=0;
		}
		if(ma==(zx[aa]-1))
			jum+=zy[aa];
		za[aa]=mp(zx[aa],zy[aa]);
	//	cout<<aa<<" "<<zy[aa]<<"@@@\n";
	//	if(TS==1)
	//		za[aa].se--;
		//return ;
	}
	else
	{
		ll moa=tim[0].fi+tim[1].fi,bww;
	//	cout<<aa<<" "<<moa<<"___\n";
		if(tim[0].fi==tim[1].fi)
		{
			ll ii,bw=0,bon=0;
			for(ii=0;ii<tim.size();ii++)
			{
				if(tim[ii].fi<tim[0].fi)
				{
					break;
				}
				//cout<<aa<<"_\n";
				bon+=bw*tim[ii].se;
			//	cout<<aa<<" "<<bon<<" "<<bw<<"#"<<tim[ii].se<<"@\n";
				bw+=tim[ii].se;
			}
			bww=bon;
			za[aa]=mp(zx[aa],bon);
		}
		else
		{
		//	cout<<aa<<"__\n";
			ll ii,bw=0,bon=0;
			for(ii=1;ii<tim.size();ii++)
			{
				if(tim[ii].fi<tim[1].fi)
				{
					break;
				}
				//cout<<aa<<"___\n";
				bon+=tim[0].se*tim[ii].se;
			}
			bww=bon;
			za[aa]=mp(zx[aa],bon);
		}
	//	cout<<aa<<"____"<<bww<<"\n";
		if(ma<moa)
		{
			ma=max(ma,moa);
			jum=0;
		}
		if(ma==moa)
			jum+=bww;
		za[aa].se=zy[aa];
	}
	//cout<<aa<<" "<<za[aa].fi<<" "<<za[aa].se<<"__\n";
}
void upd(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff,ll gg)
{
	if(aa==bb)
	{
		ST[ff][ee]=dd;
		byk[ff][ee]=gg;
	}
	else
	{
		ll ce=(aa+bb)/2;
		if(cc<=ce)
			upd(aa,ce,cc,dd,ee*2,ff,gg);
		else
			upd(ce+1,bb,cc,dd,ee*2+1,ff,gg);
		ST[ff][ee]=max(ST[ff][ee*2],ST[ff][ee*2+1]);
		byk[ff][ee]=0;
		if(ST[ff][ee]==ST[ff][ee*2])byk[ff][ee]+=byk[ff][ee*2];
		if(ST[ff][ee]==ST[ff][ee*2+1])byk[ff][ee]+=byk[ff][ee*2+1];
	}
	//cout<<ff<<" "<<aa<<" "<<bb<<" "<<ee<<"  "<<ST[ff][ee]<<" "<<byk[ff][ee]<<"\n";
}
void cari(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	if(bb<cc||dd<aa)return ;
	else
	if(cc<=aa&&bb<=dd)
		tom.pb(ee);
	else
	{
		ll ce=(aa+bb)/2;
		cari(aa,ce,cc,dd,ee*2);
		cari(ce+1,bb,cc,dd,ee*2+1);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>ta>>tb;
		v[ta].pb(tb);
		v[tb].pb(ta);
	}
	dfs(1);
	CS=cyc.size();
	memset(b,0,sizeof(b));
	for(i=0;i<CS;i++)b[cyc[i]]=1;
	for(i=0;i<CS;i++)
	{
		//b[i]=1;
		ma=-1;
		jum=0;
		dfs1(cyc[i],cyc[i],0);
		A[i]=mp(ma,jum);
		//b[i]=1;
		//cout<<cyc[i]<<" "<<A[i].fi<<" "<<A[i].se<<"\n";
	}
	ma=-1;
	jum=0;
	for(i=0;i<CS;i++)
	{
		b[cyc[i]]=0;
		dfs2(cyc[i],cyc[i]);
		b[cyc[i]]=1;
	}
	//cout<<ma<<" ) "<<jum<<"\n";
	jum*=2;
	//jum=0;
	K=CS*2-1;
	for(i=0;i<CS*2;i++)
	{
		upd(0,K,i,i+A[i%CS].fi,1,0,A[i%CS].se);
		upd(0,K,i,(K-i)+A[i%CS].fi,1,1,A[i%CS].se);
	}
	for(i=0;i<CS;i++)
	{
		ll L,R,C;
		L=i+1;R=i+(CS)/2;C=A[i].fi;
		while(L>=CS)
		{
			L-=CS;
			R-=CS;
		}
		C-=(L-1);
		tom.clear();cari(0,K,L,R,1);
	//	cout<<cyc[i]<<" "<<L<<" "<<R<<" "<<C<<"\n";
		for(j=0;j<tom.size();j++)
		{
		//	cout<<cyc[i]<<" "<<ST[0][tom[j]]+C<<"@\n";
			if(ma<(ST[0][tom[j]]+C))
			{
				ma=(ST[0][tom[j]]+C);
				jum=0;
			}
			if(ma==(ST[0][tom[j]]+C))
			{
				jum+=A[i].se*byk[0][tom[j]];
	//			cout<<cyc[i]<<" "<<ma<<" "<<jum<<"_\n";
			}
		}
		L=(i-(CS)/2);R=i-1;C=A[i].fi;
		while(L<0)
		{
			L+=CS;
			R+=CS;
		}
		C+=(R+1)-K;	
	//	cout<<cyc[i]<<"  "<<L<<" "<<R<<" "<<C<<"__\n";
		tom.clear();cari(0,K,L,R,1);
		for(j=0;j<tom.size();j++)
		{
		//	cout<<ST[1][tom[j]]+C<<"@\n";
			if(ma<(ST[1][tom[j]]+C))
			{
				ma=(ST[1][tom[j]]+C);
				jum=0;
			}
			if(ma==(ST[1][tom[j]]+C))
			{
				jum+=A[i].se*byk[1][tom[j]];
	//			cout<<cyc[i]<<" "<<ma<<" "<<jum<<"\n";
			}
		}
	}
	// for(i=0;i<CS;i++)
	// {
	// 	ll tam=1;
	// 	for(j=i+1;j<=(i+(CS)/2);j++)
	// 	{
	// 		if(ma<(tam+A[i].fi+A[j%CS].fi))
	// 		{
	// 			ma=(tam+A[i].fi+A[j%CS].fi);
	// 			jum=0;
	// 		}
	// 		if(ma==(tam+A[i].fi+A[j%CS].fi))
	// 		{
	// 		//	cout<<cyc[i]<<" "<<cyc[j%CS]<<" "<<(tam+A[i].fi+A[j%CS].fi)<<"\n";
	// 			jum+=A[i].se*A[j%CS].se;
	// 		}
	// 		tam++;
	// 	}
	// 	tam=1;
	// 	for(j=i-1;j>=(i-(CS)/2);j--)
	// 	{
	// 		if(ma<(tam+A[i].fi+A[(j+CS)%CS].fi))
	// 		{
	// 			ma=(tam+A[i].fi+A[(j+CS)%CS].fi);
	// 			jum=0;
	// 		}	
	// 		if(ma==(tam+A[i].fi+A[(j+CS)%CS].fi))
	// 		{
	// 	//		cout<<cyc[i]<<" "<<cyc[(j+CS)%CS]<<" "<<ma<<"\n";
	// 			jum+=A[i].se*A[(j+CS)%CS].se;
	// 		}
	// 		tam++;
	// 	}
	// }
	//cout<<ma<<" "<<jum<<"\n";
	jum/=2;
	cout<<jum<<"\n";
}

Compilation message (stderr)

shymbulak.cpp: In function 'void dfs(ll)':
shymbulak.cpp:19:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs1(ll, ll, ll)':
shymbulak.cpp:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs2(ll, ll)':
shymbulak.cpp:65:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
shymbulak.cpp:114:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(ii=0;ii<tim.size();ii++)
             ~~^~~~~~~~~~~
shymbulak.cpp:132:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(ii=1;ii<tim.size();ii++)
             ~~^~~~~~~~~~~
shymbulak.cpp:131:10: warning: unused variable 'bw' [-Wunused-variable]
    ll ii,bw=0,bon=0;
          ^~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:243:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tom.size();j++)
           ~^~~~~~~~~~~
shymbulak.cpp:266:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tom.size();j++)
           ~^~~~~~~~~~~

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