oj.uz

Submission #129094

# Submission time Handle Problem Language Result Execution time Memory
129094 2019-07-11T15:33:11 Z faustaadp Shymbulak (IZhO14_shymbulak) C++17
100 / 100
 252 ms 35296 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11384 KB Output is correct
2 Correct 12 ms 11384 KB Output is correct
3 Correct 12 ms 11384 KB Output is correct
4 Correct 12 ms 11384 KB Output is correct
5 Correct 12 ms 11384 KB Output is correct
6 Correct 12 ms 11384 KB Output is correct
7 Correct 16 ms 11384 KB Output is correct
8 Correct 12 ms 11384 KB Output is correct
9 Correct 12 ms 11388 KB Output is correct
10 Correct 15 ms 11384 KB Output is correct
11 Correct 15 ms 11384 KB Output is correct
12 Correct 15 ms 11384 KB Output is correct
13 Correct 12 ms 11512 KB Output is correct
14 Correct 12 ms 11512 KB Output is correct
15 Correct 13 ms 11512 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11768 KB Output is correct
2 Correct 12 ms 11640 KB Output is correct
3 Correct 13 ms 11640 KB Output is correct
4 Correct 12 ms 11520 KB Output is correct
5 Correct 15 ms 11896 KB Output is correct
6 Correct 15 ms 12136 KB Output is correct
7 Correct 15 ms 12024 KB Output is correct
8 Correct 19 ms 12028 KB Output is correct
9 Correct 18 ms 11896 KB Output is correct
10 Correct 15 ms 11896 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 20080 KB Output is correct
2 Correct 107 ms 21524 KB Output is correct
3 Correct 160 ms 34612 KB Output is correct
4 Correct 70 ms 21384 KB Output is correct
5 Correct 70 ms 21368 KB Output is correct
6 Correct 252 ms 30016 KB Output is correct
7 Correct 170 ms 25444 KB Output is correct
8 Correct 137 ms 31232 KB Output is correct
9 Correct 143 ms 30972 KB Output is correct
10 Correct 138 ms 33272 KB Output is correct
11 Correct 155 ms 34388 KB Output is correct
12 Correct 164 ms 35296 KB Output is correct