Submission #766508

#	Time	Username	Problem	Language	Result	Execution time	Memory
766508		dxz05	Shymbulak (IZhO14_shymbulak)	C++17	100 / 100	68 ms	21228 KiB

shymbulak

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;

vector<int> color;
vector<int> cycle;

stack<int> st;
bool dfs0(int v, int p){
    st.push(v);
    color[v] = 1;

    for (int u : g[v]){
        if (u == p) continue;

        if (color[u] == 0){
            if (dfs0(u, v)) return true;
        }

        if (color[u] == 1){
            while (!st.empty()){
                int x = st.top();
                st.pop();
                cycle.push_back(x);
                if (x == u) break;
            }
            return true;
        }

    }

    color[v] = 2;
    st.pop();

    return false;
}

vector<bool> incycle;

#define pii pair<int, long long>
const pii inf(-1e9, 0);

pii combine(const pii &x, const pii &y){
    if (x.first > y.first) return x;
    if (x.first < y.first) return y;
    return pii(x.first, x.second + y.second);
}

pii ans = inf;

pii dfs1(int v, int p, int d){
    pii res(d, 1);

    map<int, vector<long long>> children;
    for (int u : g[v]){
        if (u == p || incycle[u]) continue;
        pii t = dfs1(u, v, d + 1);
        res = combine(res, t);
        children[t.first].push_back(t.second);
    }

    if (!children.empty()){
        int da = children.rbegin()->first;
        vector<long long> a = children.rbegin()->second;
        da -= d;

        children.erase(--children.end());

        if ((int) a.size() >= 2){
            long long sum = accumulate(a.begin(), a.end(), 0LL);
            for (long long x : a){
                sum -= x;
                ans = combine(ans, pii(2 * da, 2 * x * sum));
            }
        } else if (!children.empty()){
            int db = children.rbegin()->first;
            vector<long long> b = children.rbegin()->second;
            db -= d;

            long long sum = accumulate(b.begin(), b.end(), 0LL);
            ans = combine(ans, pii(da + db, 2 * a.front() * sum));
        }

    }

    return res;
}

struct SegmentTree{
    int n;
    vector<pii> tree;

    void build(int v, int tl, int tr, const vector<pii> &a){
        if (tl == tr){
            tree[v] = a[tl];
        } else {
            int tm = (tl + tr) >> 1;
            build(v << 1, tl, tm, a);
            build(v << 1 | 1, tm + 1, tr, a);
            tree[v] = combine(tree[v << 1], tree[v << 1 | 1]);
        }
    }

    SegmentTree(const vector<pii> &a){
        n = (int) a.size();
        tree.assign(4 * n + 5, inf);
        build(1, 0, n - 1, a);
    }

    pii get(int v, int tl, int tr, int l, int r){
        if (l <= tl && tr <= r) return tree[v];
        if (tl > r || tr < l) return inf;
        int tm = (tl + tr) >> 1;
        return combine(get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
    }

    pii get(int l, int r){
        return get(1, 0, n - 1, l, r);
    }

};

int main(){
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    g.resize(n);
    for (int i = 0; i < n; i++){
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    color.assign(n, 0);
    dfs0(0, 0);

    int k = (int) cycle.size();

    assert(k >= 3);

    incycle.assign(n, false);
    for (int v : cycle) incycle[v] = true;

    vector<int> a(k), b(k);
    vector<pii> pos(k), neg(k);
    for (int i = 0; i < k; i++){
        int v = cycle[i];

        pii t = dfs1(v, -1, 0);
        a[i] = t.first;
        b[i] = t.second;
        pos[i] = pii(i + a[i], b[i]);
        neg[i] = pii(-i + a[i], b[i]);
    }

    SegmentTree st_pos(pos);
    SegmentTree st_neg(neg);

    int h = k / 2;
    for (int i = 0; i < k; i++){ // case one
        int tl = (i + 1) % k, tr = (i + h) % k;

        vector<pair<int, int>> seg;
        if (tl <= tr){
            seg.emplace_back(tl, tr);
        } else {
            seg.emplace_back(tl, n - 1);
            seg.emplace_back(0, tr);
        }

        for (auto [l, r] : seg){
            pii t = st_pos.get(l, r);
            if (l > i){ // i .. l .. r
                t.first += -i + a[i];
            } else { // l .. r .. i
                t.first += k - i + a[i];
            }
            t.second *= b[i];
            ans = combine(ans, t);
        }
    }

    for (int i = 0; i < k; i++){ // case two
        int tl = (i - h + k) % k, tr = (i - 1 + k) % k;

        vector<pair<int, int>> seg;
        if (tl <= tr){
            seg.emplace_back(tl, tr);
        } else {
            seg.emplace_back(tl, n - 1);
            seg.emplace_back(0, tr);
        }

        for (auto [l, r] : seg){
            pii t = st_neg.get(l, r);
            if (r < i){ // l .. r .. i
                t.first += i + a[i];
            } else { // i .. l .. r
                t.first += k + i + a[i];
            }
            t.second *= b[i];
            ans = combine(ans, t);
        }
    }

    cout << ans.second / 2 << endl;

    return 0;
}

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