Submission #174701

#	Time	Username	Problem	Language	Result	Execution time	Memory
174701		emil_physmath	Shymbulak (IZhO14_shymbulak)	C++17	0 / 100	53 ms	8184 KiB

shymbulak

#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)
                         ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50