oj.uz

답안 #766470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766470 2023-06-25T16:58:30 Z dxz05 관광지 (IZhO14_shymbulak) C++17
0 / 100
 24 ms 5892 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 dfs1(int v, int p, int d){
    color[v] = 1;

    pii res(d, 1);
    for (int u : g[v]){
        if (u == p || incycle[u]) continue;
        res = combine(res, dfs1(u, v, d + 1));
    }

    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;

    color.assign(n, 0);

    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);

    pii ans = inf;

    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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 5892 KB Output isn't correct
2 Halted 0 ms 0 KB -