oj.uz

답안 #128519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128519 2019-07-11T05:28:12 Z faustaadp 관광지 (IZhO14_shymbulak) C++17
50 / 100
 1500 ms 11892 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[101010],b[101010],CS,ma,jum,has,j;
vector<ll> v[101010],cyc,isi[101010];
pair<ll,ll> A[101010];
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);
	}
}
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;
	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:15: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:47: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:65: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:99:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<isi[i].size();j++)
           ~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5852 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 7 ms 5880 KB Output is correct
5 Correct 7 ms 5880 KB Output is correct
6 Correct 7 ms 5880 KB Output is correct
7 Correct 7 ms 5880 KB Output is correct
8 Correct 7 ms 5880 KB Output is correct
9 Correct 7 ms 5880 KB Output is correct
10 Correct 7 ms 5880 KB Output is correct
11 Correct 7 ms 5884 KB Output is correct
12 Correct 7 ms 5880 KB Output is correct
13 Correct 7 ms 5880 KB Output is correct
14 Correct 9 ms 5880 KB Output is correct
15 Correct 7 ms 6008 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 6008 KB Output is correct
2 Correct 12 ms 6008 KB Output is correct
3 Correct 11 ms 6008 KB Output is correct
4 Correct 9 ms 6008 KB Output is correct
5 Correct 24 ms 6136 KB Output is correct
6 Correct 213 ms 6324 KB Output is correct
7 Correct 590 ms 6340 KB Output is correct
8 Correct 481 ms 6264 KB Output is correct
9 Correct 14 ms 6264 KB Output is correct
10 Correct 91 ms 6264 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1550 ms 11892 KB Time limit exceeded
2 Halted 0 ms 0 KB -