#include <iostream>
#include <vector>
using namespace std;
typedef long long llong;
vector<int> nei[200005];
pair<int, int> tx[800000], ty[800000];
template<class T1, class T2>
ostream& operator<<(ostream& ostr, const pair<T1, T2>& a)
{
return ostr << "{" << a.first << ", " << a.second << "}";
}
void Add(pair<int, int>* a, const pair<int, int>& rhs)
{
if (rhs.first > a->first)
*a = rhs;
else if (rhs.first == a->first)
a->second += rhs.second;
}
namespace Decomp
{
bool used[200005];
bool root[200005];
vector<int> line;
bool FindCycle(int v, int par)
{
used[v] = true;
for (int to: nei[v])
{
if (to == par) continue;
if (used[to])
{
line.push_back(v);
root[v] = true;
return true;
}
if (FindCycle(to, v))
{
line.push_back(v);
root[v] = true;
return true;
}
}
return false;
}
pair<int, int> DFS(int v, int par)
{
// cerr << "v: " << v << "\tpar: " << par << endl;
pair<int, int> res = {0, 1};
for (int to: nei[v])
if (to != par && !root[to])
{
pair<int, int> p = DFS(to, v);
++p.first;
Add(&res, p);
}
return res;
}
void Decompose(vector<pair<int, int>>* res)
{
FindCycle(1, -1);
#ifdef DEBUG
cerr << line.size() << endl;
for (int v: line)
cerr << v << ' ';
cerr << '\n';
#endif
res->resize(line.size());
for (int i = 0; i < line.size(); ++i)
{
(*res)[i] = DFS(line[i], -1);
#ifdef DEBUG
cerr << line[i] << ": " << (*res)[i] << '\n';
#endif
}
}
};
void Build(pair<int, int>* t, int v, int vl, int vr, const vector<pair<int, int>>& a)
{
if (vl == vr)
{
t[v] = a[vr];
return;
}
int vm = (vl + vr) / 2;
Build(t, v * 2, vl, vm, a);
Build(t, v * 2 + 1, vm + 1, vr, a);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
pair<int, int> Max(pair<int, int>* t, int v, int vl, int vr, int l, int r)
{
if (vl == l && vr == r)
return t[v];
int vm = (vl + vr) / 2;
if (r <= vm)
return Max(t, v * 2, vl, vm, l, r);
else if (l > vm)
return Max(t, v * 2 + 1, vm + 1, vr, l, r);
return max(Max(t, v * 2, vl, vm, l, vm),
Max(t, v * 2 + 1, vm + 1, vr, vm + 1, r));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int nodes;
cin >> nodes;
for (int i = 0; i < nodes; ++i)
{
int u, v;
cin >> u >> v;
nei[u].push_back(v);
nei[v].push_back(u);
}
vector<pair<int, int>> a;
Decomp::Decompose(&a);
int n = a.size();
vector<pair<int, int>> x(n), y(n);
for (int i = 0; i < n; ++i)
{
x[i] = {i + a[i].first, a[i].second};
y[i] = {n - i + a[i].first, a[i].second};
#ifdef DEBUG
cerr << "i: " << i << ": x = " << x[i] << " y = " << y[i] << endl;
#endif
}
Build(tx, 1, 0, n - 1, x);
Build(ty, 1, 0, n - 1, y);
pair<int, int> res(0, 1);
for (int l = 0; l + 1 < n; ++l)
{
int s = l + 1;
int e = l + n / 2;
if (n % 2 == 0) --e;
e = min(e, n - 1);
if (s <= e)
{
pair<int, int> mx = Max(tx, 1, 0, n - 1, s, e);
Add(&res, {mx.first - l + a[l].first, mx.second * a[l].second});
}
s = l + n / 2 + 1;
e = n - 1;
if (s <= e)
{
pair<int, int> mx = Max(ty, 1, 0, n - 1, s, e);
Add(&res, {mx.first + l + a[l].first, mx.second * a[l].second});
}
if (n % 2 == 0 && l + n / 2 < n)
{
pair<int, int> cur = a[l + n / 2];
Add(&res, {cur.first + a[l].first + n / 2, 2 * cur.second * a[l].second});
}
}
cout << res.second << endl;
}
Compilation message
shymbulak.cpp: In function 'void Decomp::Decompose(std::vector<std::pair<int, int> >*)':
shymbulak.cpp:70:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < line.size(); ++i)
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5240 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
9208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
