Submission #766500

# Submission time Handle Problem Language Result Execution time Memory
766500 2023-06-25T17:24:18 Z dxz05 Shymbulak (IZhO14_shymbulak) C++17
50 / 100
1500 ms 20800 KB
#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);

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

    int sz = (int) children.size();

    for (int i = 0; i < sz; i++){
        for (int j = i + 1; j < sz; j++){
            auto x = children[i], y = children[j];
            
            pii t;
            t.first = x.first + y.first - 2 * d;
            t.second = 2 * x.second * y.second;
            ans = combine(ans, t);
        }
    }

    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;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 648 KB Output is correct
6 Correct 33 ms 852 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 33 ms 5824 KB Output is correct
2 Correct 49 ms 6572 KB Output is correct
3 Correct 70 ms 20800 KB Output is correct
4 Correct 25 ms 7500 KB Output is correct
5 Correct 28 ms 7376 KB Output is correct
6 Correct 65 ms 13140 KB Output is correct
7 Correct 67 ms 10608 KB Output is correct
8 Correct 56 ms 14668 KB Output is correct
9 Correct 56 ms 14764 KB Output is correct
10 Correct 59 ms 16284 KB Output is correct
11 Execution timed out 1571 ms 18708 KB Time limit exceeded
12 Halted 0 ms 0 KB -