#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
int n;
vector<int> con[200005];
bool visited[200005];
int parent[200005];
bool iscyc[200005];
int maxd[200005];
int cntmax[200005];
int depth[200005];
int tin[200005];
int tout[200005];
int timer;
bool gasit=0;
pair<int,int> capete;
int maxdist=0,cate=0;
vector<int> cyc;
bool isanc(int x, int y)
{
if(tin[x]<=tin[y] && tout[x]>=tout[y])
return 1;
return 0;
}
void dfs_find(int nod)
{
//if(gasit) return;
tin[nod]=++timer;
visited[nod]=1;
for(auto adj:con[nod])
{
if(!visited[adj])
{
parent[adj]=nod;
dfs_find(adj);
}
else if(adj!=parent[nod]) ///am gasit cyclu
{
if(gasit && (capete.first != adj || capete.second != nod))
{
while(1)
n=0;
}
gasit=1;
capete = {nod,adj};
}
}
tout[nod]=++timer;
}
void find_cycle()
{
dfs_find(1);
if(!gasit)
{
while(1)
n=0;
}
while(!isanc(capete.first,capete.second))
{
cyc.push_back(capete.first);
capete.first = parent[capete.first];
}
cyc.push_back(capete.first);
vector<int> aux;
while(capete.second!=capete.first)
{
aux.push_back(capete.second);
capete.second = parent[capete.second];
}
reverse(aux.begin(),aux.end());
for(auto x:aux)
cyc.push_back(x);
for(auto x:cyc)
iscyc[x]=1;
/*cout<<"cycle: ";
for(auto x:cyc)
cout<<x<<" ";
cout<<"\n";*/
}
void dfs2(int nod, int par)
{
maxd[nod] = depth[nod];
cntmax[nod] = 1;
vector<pair<int,int>> v;
for(auto adj:con[nod])
{
if(adj!=par && !iscyc[adj])
{
depth[adj]=depth[nod]+1;
dfs2(adj,nod);
v.push_back({maxd[adj] - depth[nod], cntmax[adj]});
if(maxd[adj]>maxd[nod])
{
maxd[nod] = maxd[adj];
cntmax[nod] = cntmax[adj];
}
else if(maxd[adj]==maxd[nod])
cntmax[nod] += cntmax[adj];
}
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
if((int)v.size()>1 && v[0].first + v[1].first >= maxdist)
{
if(v[0].first==v[1].first)
{
int cntpref = v[0].second;
for(int i=1;i<v.size();i++)
{
if(v[i]!=v[0])
break;
if(2*v[0].first > maxdist)
{
maxdist = 2*v[0].first;
cate = v[i].second * cntpref;
}
else if(2*v[0].first == maxdist)
cate += v[i].second * cntpref;
cntpref += v[i].second;
}
}
else
{
/*for(int i=1;i<v.size();i++)
{
if(v[i]!=v[1])
break;
if(v[0].first + v[1].first > maxdist)
{
maxdist = v[0].first + v[1].first;
cate = v[i].second * v[0].second;
}
else if(v[0].first + v[1].first == maxdist)
cate += v[i].second * v[0].second;
}*/
for(int i=0;i<v.size();i++)
{
for(int j=i+1;j<v.size();j++)
{
if(v[i].first + v[j].first > maxdist)
{
maxdist = v[i].first + v[j].first;
cate = v[i].second * v[j].second;
}
else if(v[i].first + v[j].first == maxdist)
cate += v[i].second * v[j].second;
}
}
}
}
}
signed main()
{
cin>>n;
int a,b;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
if(a==b)
{
while(1)
n=0;
}
con[a].push_back(b);
con[b].push_back(a);
}
find_cycle();
for(int i=0;i<cyc.size();i++)
{
depth[cyc[i]]=0;
dfs2(cyc[i],0);
if(maxd[cyc[i]] > maxdist)
{
maxdist = maxd[cyc[i]];
cate = cntmax[cyc[i]];
}
else if(maxd[cyc[i]] == maxdist)
cate += cntmax[cyc[i]];
}
for(int i=0;i<cyc.size();i++)
{
for(int j=i+1;j<cyc.size();j++)
{
if(min(j-i, i + 1 + (int)cyc.size()-1-j) + maxd[cyc[i]] + maxd[cyc[j]] > maxdist)
{
maxdist = min(j-i,i + 1 + (int)cyc.size()-1-j) + maxd[cyc[i]] + maxd[cyc[j]];
if(j-i != i + 1 + (int)cyc.size()-1-j) cate = cntmax[cyc[i]] * cntmax[cyc[j]];
else cate = 2LL * cntmax[cyc[i]] * cntmax[cyc[j]];
}
else if(min(j-i,i + 1 + (int)cyc.size()-1-j) + maxd[cyc[i]] + maxd[cyc[j]] == maxdist)
{
if(j-i != i + 1 + (int)cyc.size()-1-j) cate += cntmax[cyc[i]] * cntmax[cyc[j]];
else cate += 2LL * cntmax[cyc[i]] * cntmax[cyc[j]];
}
}
}
// cout<<"maxdist: "<<maxdist<<"\n";
cout<<cate;
return 0;
}
Compilation message
shymbulak.cpp: In function 'void dfs2(long long int, long long int)':
shymbulak.cpp:110:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i=1;i<v.size();i++)
| ~^~~~~~~~~
shymbulak.cpp:138:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
shymbulak.cpp:140:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int j=i+1;j<v.size();j++)
| ~^~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:170:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | for(int i=0;i<cyc.size();i++)
| ~^~~~~~~~~~~
shymbulak.cpp:182:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
182 | for(int i=0;i<cyc.size();i++)
| ~^~~~~~~~~~~
shymbulak.cpp:184:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for(int j=i+1;j<cyc.size();j++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14492 KB |
Output is correct |
| 4 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
3 ms |
14736 KB |
Output is correct |
| 6 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 7 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 8 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 9 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 10 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 11 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 12 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 13 |
Correct |
3 ms |
14680 KB |
Output is correct |
| 14 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 15 |
Correct |
3 ms |
14684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
6 ms |
14940 KB |
Output is correct |
| 6 |
Correct |
5 ms |
15196 KB |
Output is correct |
| 7 |
Correct |
5 ms |
14940 KB |
Output is correct |
| 8 |
Correct |
5 ms |
14940 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14948 KB |
Output is correct |
| 10 |
Correct |
5 ms |
14940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
18892 KB |
Output is correct |
| 2 |
Correct |
60 ms |
18772 KB |
Output is correct |
| 3 |
Correct |
1461 ms |
21204 KB |
Output is correct |
| 4 |
Correct |
64 ms |
19536 KB |
Output is correct |
| 5 |
Correct |
65 ms |
19804 KB |
Output is correct |
| 6 |
Correct |
135 ms |
24656 KB |
Output is correct |
| 7 |
Correct |
92 ms |
22100 KB |
Output is correct |
| 8 |
Correct |
117 ms |
24788 KB |
Output is correct |
| 9 |
Correct |
131 ms |
24660 KB |
Output is correct |
| 10 |
Correct |
138 ms |
25596 KB |
Output is correct |
| 11 |
Correct |
113 ms |
29464 KB |
Output is correct |
| 12 |
Correct |
128 ms |
29812 KB |
Output is correct |
