#include <bits/stdc++.h>
#pragma optimize ("-Ofast")
#define ld long double
#define ll long long
#define F first
#define S second
#define pb push_back
#define mp make_pair
using namespace std;
const ll inf = 1e18 + 18;
const int maxn = 200005;
int used[maxn];
bool cycle[maxn];
pair <int, int> cc[maxn]; // {len, cnt}
vector <int> g[maxn];
int cyclesz = 0;
vector <int> path;
bool f = false;
void findcycle(int v, int pr)
{
used[v] = 1;
path.pb(v);
for(int to:g[v])
{
if (used[to] == 0)
{
findcycle(to, v);
if (f) return; //
}
if (used[to] == 1 && pr != to)
{
f = true;
cycle[to] = true;
cyclesz = 1;
while(path.back() != to)
{
cycle[path.back()] = true;
path.pop_back();
cyclesz++;
}
return;
}
}
path.pop_back();
used[v] = 2;
return;
}
int len = 0;
ll ans = 0; //ll
pair <int, int> dfs(int v, int pr)
{
vector <pair <int, ll>> vc;
vc.pb({0, 1});
for(int to:g[v])
{
if (to != pr && !cycle[to])
{
vc.pb(dfs(to, v));
vc.back().F++;
}
}
sort(vc.rbegin(), vc.rend());
int n = int(vc.size());
int i = 0;
if (n == 1)
{
return vc[0];
}
if (vc[0].F == vc[1].F && vc[0].F * 2 >= len)
{
ll izm = 0;
ll sum = 0;
while(i < n && vc[i].F == vc[0].F)
{
sum += vc[i].S;
// cerr << vc[i].S;
i++;
}
i = 0;
while(i < n && vc[i].F == vc[0].F)
{
izm += vc[i].S * (sum - vc[i].S);
i++;
}
if (vc[0].F * 2 > len)
{
len = vc[0].F * 2;
ans = izm;
}
else
{
ans += izm;
}
}
else
if (vc[0].F != vc[1].F && vc[0].F + vc[1].F >= len)
{
ll izm = 0;
i = 1;
while(i < n && vc[i].F == vc[1].F)
{
izm += vc[0].S * vc[i].S;
i++;
}
if (vc[0].F + vc[1].F > len)
{
ans = izm * 2;
}
else
{
ans += izm * 2;
}
len = vc[0].F + vc[1].F;
}
i = 0;
ll ret = 0;
while(i < n && vc[i].F == vc[0].F)
{
ret += vc[i].S;
i++;
}
return {vc[0].F, ret};
}
main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
x--;
y--;
g[x].pb(y);
g[y].pb(x);
}
findcycle(0, 0);
for(int i = 0; i < n; i++)
{
if (cycle[i])
{
pair <int, int> pp = dfs(i, i);
cc[i] = pp;
}
}
for(int i = 0; i < n; i++)
{
if (cycle[i])
{
for(int j:g[i])
{
if (cycle[j])
{
//obhod
int v = j;
int pr = i;
int LEN = cc[i].F;
int CNT = cc[i].S;
int t = cyclesz / 2;
for(t; t > 0; t--)
{
LEN++;
if (LEN + cc[v].F > len)
{
len = LEN + cc[v].F;
ans = CNT * cc[v].S;
}
else
if (LEN + cc[v].F == len)
{
ans += CNT * cc[v].S;
}
for(auto ttt:g[v])
{
if (cycle[ttt] && ttt != pr)
{
pr = v;
v = ttt;
break;
}
}
}
}
}
}
}
// cerr << len << endl;
cout << (ans >> 1);
return 0;
}
Compilation message
shymbulak.cpp:3:0: warning: ignoring #pragma optimize [-Wunknown-pragmas]
#pragma optimize ("-Ofast")
shymbulak.cpp:134:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:180:26: warning: statement has no effect [-Wunused-value]
for(t; t > 0; t--)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 5 |
Correct |
6 ms |
4964 KB |
Output is correct |
| 6 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 9 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 10 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 11 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 12 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 13 |
Correct |
6 ms |
4864 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
6 ms |
5120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5196 KB |
Output is correct |
| 3 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5248 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5504 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5248 KB |
Output is correct |
| 8 |
Correct |
9 ms |
5248 KB |
Output is correct |
| 9 |
Correct |
8 ms |
5248 KB |
Output is correct |
| 10 |
Correct |
8 ms |
5248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
8392 KB |
Output is correct |
| 2 |
Correct |
100 ms |
8988 KB |
Output is correct |
| 3 |
Execution timed out |
1530 ms |
12916 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
