#include<stdio.h>
#include<vector>
#include<queue>
std::vector<int> map[200001];
int deg[200001];
int n;
int dist[200001], distC[200001];
int v[200001];
int cycles[200001], CC = 0;
inline int cn(int x){return dist[cycles[(x)%CC]];}
inline int cd(int x){return distC[cycles[(x)%CC]];}
int main()
{
int i, x, xx;
scanf("%d", &n);
for(i=1; i<=n; i++)
{
scanf("%d%d", &x, &xx);
map[x].push_back(xx);
map[xx].push_back(x);
deg[x]++;
deg[xx]++;
}
std::queue<int> Q;
for(i=1; i<=n; i++)
{
if(deg[i] == 1)Q.push(i);
distC[i] = 1;
}
while(!Q.empty())
{
x = Q.front();
Q.pop();
v[x] = true;
for(int t :map[x]) if(v[t] == false){ xx=t; break; }
deg[xx]--;
if(deg[xx] == 1) Q.push(xx);
if(dist[xx] < dist[x]+1)
{
dist[xx] = dist[x]+1;
distC[xx] = distC[x];
}
else if(dist[xx] == dist[x] + 1) distC[xx]+=distC[x];
}
for(i=1; i<=n; i++) if(deg[i] != 1) break;
xx = x = i;
do
{
v[xx] = true;
cycles[CC++] = xx;
int tx=-1;
for(int t: map[xx]) if(!v[t]){ tx = t; break;}
xx = tx;
}while(xx!=-1);
int max;
long long C;
max = C = 0;
int Allmax;
long long AllC;
int j;
for(j=1; j-i<=CC-j; j++)
{
if(cn(j)+j > max)
{
max = cn(j)+j;
C = cd(j);
}
else if(cn(j)+j == max) C+=cd(j);
}
Allmax = max + cn(0);
AllC = 1ll*C*cd(0);
for(i=1; i<CC; i++)
{
max --;
if(cn(j)+j-i > max)
{
max = cn(j)+j-i;
C = cd(j);
}
else if(cn(j)+j-i == max) C+=cd(j);
if(max + cn(i) > Allmax)
{
Allmax = max+cn(i);
AllC = 1ll*cd(i)*C;
}
else if(max +cn(i) == Allmax)
{
AllC += 1ll*cd(i)*C;
}
j++;
}
printf("%lld", AllC);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
10176 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
10176 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
10176 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
10176 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
10176 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
10176 KB |
Output isn't correct |
| 7 |
Incorrect |
0 ms |
10176 KB |
Output isn't correct |
| 8 |
Correct |
0 ms |
10176 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
10176 KB |
Output isn't correct |
| 10 |
Incorrect |
0 ms |
10176 KB |
Output isn't correct |
| 11 |
Correct |
0 ms |
10176 KB |
Output is correct |
| 12 |
Correct |
2 ms |
10176 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
10176 KB |
Output isn't correct |
| 14 |
Incorrect |
0 ms |
10176 KB |
Output isn't correct |
| 15 |
Correct |
2 ms |
10176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
10176 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
10176 KB |
Output isn't correct |
| 3 |
Correct |
0 ms |
10176 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
10176 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
10308 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
10308 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
10308 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
10308 KB |
Output isn't correct |
| 9 |
Correct |
2 ms |
10308 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
10308 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
13340 KB |
Output isn't correct |
| 2 |
Incorrect |
57 ms |
13740 KB |
Output isn't correct |
| 3 |
Correct |
52 ms |
13344 KB |
Output is correct |
| 4 |
Correct |
53 ms |
13472 KB |
Output is correct |
| 5 |
Incorrect |
39 ms |
13604 KB |
Output isn't correct |
| 6 |
Incorrect |
114 ms |
16112 KB |
Output isn't correct |
| 7 |
Incorrect |
74 ms |
15188 KB |
Output isn't correct |
| 8 |
Correct |
78 ms |
16904 KB |
Output is correct |
| 9 |
Incorrect |
87 ms |
16904 KB |
Output isn't correct |
| 10 |
Correct |
73 ms |
17304 KB |
Output is correct |
| 11 |
Incorrect |
82 ms |
17804 KB |
Output isn't correct |
| 12 |
Incorrect |
96 ms |
18200 KB |
Output isn't correct |
