#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)
{
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++)
{
for(j=0;j<isi[i].size();j++)
dfs2(isi[i][j],isi[i][j],0);
}
for(i=0;i<CS;i++)
{
ll tam=0;
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]<<" "<<ma<<"\n";
jum+=A[i].se*A[j%CS].se;
}
tam++;
}
tam=0;
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:64: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:97:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<isi[i].size();j++)
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
6008 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1550 ms |
12068 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
