Submission #174701

#TimeUsernameProblemLanguageResultExecution timeMemory
174701emil_physmathShymbulak (IZhO14_shymbulak)C++17
0 / 100
53 ms8184 KiB
#include <iostream> #include <vector> using namespace std; typedef long long llong; pair<int, int> answer(0, 1); 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> way[2] = {{0, 1}, {0, 1}}; 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; if (p.first == way[1].first) Add(way + 1, p); else if (p.first == way[0].first) Add(way, p); else { if (p.first > way[0].first) { swap(way[0], way[1]); way[1] = p; } else if (p.first > way[1].first) way[1] = p; } Add(&res, p); } if (way[0].second > 1) Add(&answer, {2 * way[0].first, ((way[0].second - 1) * way[0].second) / 2}); else Add(&answer, {way[0].first + way[1].first, way[0].second * way[1].second}); 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); 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(&answer, {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(&answer, {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(&answer, {cur.first + a[l].first + n / 2, 2 * cur.second * a[l].second}); } } cout << answer.second << endl; }

Compilation message (stderr)

shymbulak.cpp: In function 'void Decomp::Decompose(std::vector<std::pair<int, int> >*)':
shymbulak.cpp:90:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < line.size(); ++i)
                         ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...