답안 #175688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
175688 2020-01-07T09:48:30 Z emil_physmath 관광지 (IZhO14_shymbulak) C++17
100 / 100
217 ms 21784 KB
// #define DEBUG
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long llong;
#define ALL_LL
#ifdef ALL_LL
#define int llong
#endif

pair<int, int> answer(0, 1);
vector<int> nei[200001];
pair<int, int> tx[800000], ty[800000];

template<typename T>
inline T Comb2(T x) { return ((x - (T)1) * x) / (T)2; }
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[200001];
    bool root[200001];
    pair<int, int> ray[200001];
    vector<int> line;
    int 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 to;
            }
            if (int ret = FindCycle(to, v))
            {
                line.push_back(v);
                root[v] = true;
                if (v == ret)
                    return 0;
                return ret;
            }
        }
        return 0;
    }
    void DFS(int v, int par)
    {
        // cerr << "v: " << v << "\tpar: " << par << endl;
        ray[v] = make_pair(0, 1);
        for (int to: nei[v])
            if (to != par && !root[to])
            {
                DFS(to, v);
                pair<int, int> p = ray[to];
                ++p.first;
                Add(ray + v, p);
            }
    }
    void AddWays(int v, int par)
    {
        vector<pair<int, int>> chld;
        chld.reserve(nei[v].size());
        for (int to: nei[v])
            if (to != par && !root[to])
            {
                AddWays(to, v);
                chld.push_back({ray[to].first + 1, ray[to].second});
            }
        if (chld.size() < 2)
            return;
        sort(chld.begin(), chld.end(), greater<pair<int, int>>());
        int i = 2;
        while (i < chld.size() && chld[i].first == chld[i - 1].first)
            ++i;
        if (i < chld.size()) chld.erase(chld.begin() + i, chld.end());
        /*cerr << "v: " << v << "`   chld: ";
        for (auto it: chld)
            cerr << it << ' ';
        cerr << endl;*/
        if (chld[0].first == chld[1].first)
        {
            pair<int, int> cur = {2 * chld[0].first, 0};
            int sum = 0;
            for (const pair<int, int>& p: chld)
            {
                cur.second -= Comb2(p.second);
                // if (v == 1)
                    // cerr << "delta -" << Comb2(p.second) << endl;
                sum += p.second;
            }
            cur.second += Comb2(sum);
            // if (v == 1)
                // cerr << "v: 1, cur: " << cur << endl;
            Add(&answer, cur);
        }
        else
        {
            int sum = 0;
            for (int i = 1; i < chld.size(); ++i)
                sum += chld[i].second;
            pair<int, int> cur = {chld[0].first + chld[1].first, chld[0].second * sum};
            Add(&answer, cur);
        }
    }
    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)
        {
            DFS(line[i], -1);
            AddWays(line[i], -1);
            (*res)[i] = ray[line[i]];
#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] = t[v * 2];
    Add(t + v, 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);
    pair<int, int> res = Max(t, v * 2, vl, vm, l, vm);
    Add(&res, Max(t, v * 2 + 1, vm + 1, vr, vm + 1, r));
    return res;
}
#ifdef ALL_LL
#undef int
#endif // ALL_LL
int main()
#ifdef ALL_LL
#define int llong
#endif // ALL_LL
{
    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] << "   a[i] = " << a[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;
        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 + 1) / 2;
        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});
        }
    }
    // cerr << answer.first<< ' ';
    cout << answer.second << endl;
}
/*
19
6 2
6 4
1 4
1 5
2 3
6 7
7 8
7 9
6 10
10 11
11 12
8 13
9 14
3 15
10 16
16 17
16 18
2 19
4 19

6
6 2
6 4
1 4
1 5
2 3
2 4
*/

Compilation message

shymbulak.cpp: In function 'void Decomp::AddWays(llong, llong)':
shymbulak.cpp:86:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i < chld.size() && chld[i].first == chld[i - 1].first)
                ~~^~~~~~~~~~~~~
shymbulak.cpp:88:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < chld.size()) chld.erase(chld.begin() + i, chld.end());
             ~~^~~~~~~~~~~~~
shymbulak.cpp:112:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 1; i < chld.size(); ++i)
                             ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void Decomp::Decompose(std::vector<std::pair<long long int, long long int> >*)':
shymbulak.cpp:128:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < line.size(); ++i)
                         ~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5084 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5052 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5084 KB Output is correct
9 Correct 2 ms 5124 KB Output is correct
10 Correct 5 ms 4984 KB Output is correct
11 Correct 4 ms 5112 KB Output is correct
12 Correct 6 ms 4984 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 5 ms 5132 KB Output is correct
15 Correct 6 ms 5112 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5180 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 5 ms 5112 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 8 ms 5488 KB Output is correct
7 Correct 9 ms 5468 KB Output is correct
8 Correct 9 ms 5368 KB Output is correct
9 Correct 9 ms 5364 KB Output is correct
10 Correct 8 ms 5496 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 10744 KB Output is correct
2 Correct 95 ms 10788 KB Output is correct
3 Correct 70 ms 19824 KB Output is correct
4 Correct 54 ms 10608 KB Output is correct
5 Correct 53 ms 11740 KB Output is correct
6 Correct 217 ms 18124 KB Output is correct
7 Correct 141 ms 14864 KB Output is correct
8 Correct 99 ms 18464 KB Output is correct
9 Correct 109 ms 18676 KB Output is correct
10 Correct 103 ms 19960 KB Output is correct
11 Correct 152 ms 21012 KB Output is correct
12 Correct 152 ms 21784 KB Output is correct