Submission #128744

#	Time	Username	Problem	Language	Result	Execution time	Memory
128744		faustaadp	Shymbulak (IZhO14_shymbulak)	C++17	50 / 100	1562 ms	17396 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];
ll ST[2][1601601];
ll byk[2][1601601];
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,ll cc)
{
	//cout<<isi[i][j]<<" "<<aa<<" "<<cc<<"_\n";
	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;
		dfs2(v[aa][ii],aa,cc+1);
	}
}
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++)
	{
		ma=-1;
		jum=0;
		dfs1(cyc[i],cyc[i],0);
		A[i]=mp(ma,jum);
		//cout<<cyc[i]<<" "<<A[i].fi<<" "<<A[i].se<<"\n";
	}
	ma=-1;
	jum=0;
	for(i=0;i<CS;i++)
	{
		b[cyc[i]]=0;
		for(j=0;j<isi[i].size();j++)
		{
			//cout<<isi[i][j]<<"\n";
			dfs2(isi[i][j],isi[i][j],0);
		}
		b[cyc[i]]=1;
	}
	//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:17: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:49: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, ll)':
shymbulak.cpp:67:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:135:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<isi[i].size();j++)
           ~^~~~~~~~~~~~~~
shymbulak.cpp:161:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tom.size();j++)
           ~^~~~~~~~~~~
shymbulak.cpp:184: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: 0 / 50