#include <bits/stdc++.h>
#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];
int depth[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 maxdepth;
int maxdepth2;
int cnt;
int cnt2;
void dfs(int v, int pr, int Depth)
{
if (Depth > maxdepth && int(g[v].size() == 1))
{
maxdepth2 = maxdepth;
maxdepth = Depth;
cnt2 = cnt;
cnt = 1;
}
else
if (Depth == maxdepth && int(g[v].size() == 1))
{
maxdepth2 = maxdepth;
cnt++;
}
depth[v] = Depth;
for(int to:g[v])
{
if (to != pr && !cycle[to])
{
dfs(to, v, Depth + 1);
}
}
return;
}
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;
int len = 0;
int ans = 0; //ll
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])
{
maxdepth = 0;
maxdepth2 = 0;
cnt = 1;
cnt2 = 1;
dfs(i, i, 0);
cc[i] = {maxdepth, cnt};
if (maxdepth + maxdepth2 > len)
{
len = maxdepth + maxdepth2;
if (maxdepth2 < maxdepth)ans = cnt * cnt2;
else ans = cnt * (cnt - 1);
}
else
if (maxdepth + maxdepth2 == len)
{
if (maxdepth2 < maxdepth) ans += cnt * cnt2;
else ans += cnt * (cnt - 1);
}
}
}
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 >> 1);
for(t; t > 0; t--)
{
LEN++;
int to = -1;
for(auto ttt:g[v])
{
if (cycle[ttt] && ttt != pr)
{
to = ttt;
break;
}
}
if (to < 0) return 112;
if (LEN + cc[to].F > len)
{
len = LEN + cc[to].F;
ans = CNT * cc[to].S;
}
else
if (LEN + cc[to].F == len)
{
ans += CNT * cc[to].S;
}
}
}
}
}
}
// cerr << len << endl;
cout << (ans >> 1);
return 0;
}
Compilation message
shymbulak.cpp:87:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:151:26: warning: statement has no effect [-Wunused-value]
for(t; t > 0; t--)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5248 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5148 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
8696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
