제출 #343713

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343713		apostoldaniel854	관광지 (IZhO14_shymbulak)	C++14	100 / 100	179 ms	25700 KiB

shymbulak

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

/**
- we have a single cycle in this graph
- we calculate the maximum depth and its count in every tree spanning from the cycle
- we use a segmentree on a cyclic vector (we will double it)
- now we solve independently for every tree spaning from the cycle
**/

const int MAX_N = 2e5;
vector <int> cycle;
int state[1 + MAX_N];
bool fix[1 + MAX_N];
vector <int> v;
vector <int> gr[1 + MAX_N];

void dfs_cycle (int node, int par) {
    state[node] = 1;
    v.pb (node);
    for (int vec : gr[node])
        if (vec != par) {
            if (state[vec] == 0)
                dfs_cycle (vec, node);
            else if (state[vec] == 1) {
                int idx = ((int) v.size ()) - 1;
                while (idx >= 0 && v[idx] != vec) {
                    cycle.pb (v[idx]);
                    idx--;
                }
                cycle.pb (vec);
            }
        }
    v.pop_back ();
    state[node] = 2;
}


struct Node {
    int value;
    ll cnt;
};

Node max_depth[1 + MAX_N];
Node ans;

Node join (Node l, Node r) {
    Node x;
    x = l;
    if (x.value == r.value)
        x.cnt += r.cnt;
    else if (x.value < r.value)
        x = r;
    return x;
}

void dfs_depth (int node, int par) {
    max_depth[node] = {0, 1};
    for (int son : gr[node])
        if (son != par && not fix[son]) {
            dfs_depth (son, node);
            ans = join (ans, {max_depth[node].value + max_depth[son].value + 1, max_depth[node].cnt * max_depth[son].cnt});
            max_depth[node] = join (max_depth[node], {max_depth[son].value + 1, max_depth[son].cnt});
        }
}
struct LazySegTree {
    vector <Node> seg;
    vector <int> lazy;
    int n;
    LazySegTree (int n) {
        this->n = n;
        seg.resize (1 + 4 * n);
        lazy.resize (1 + 4 * n);
    }
    void push (int node) {
        if (lazy[node]) {
            int left_node = node * 2, right_node = node * 2 + 1;
            seg[left_node].value += lazy[node];
            seg[right_node].value += lazy[node];
            lazy[left_node] += lazy[node];
            lazy[right_node] += lazy[node];
            lazy[node] = 0;
        }
    }
    void build (int node, int lb, int rb, vector <Node> &v) {
        if (lb == rb) {
            seg[node] = {v[lb - 1].value + lb - 1, v[lb - 1].cnt};
            return;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        build (left_node, lb, mid, v);
        build (right_node, mid + 1, rb, v);
        seg[node] = join (seg[left_node], seg[right_node]);
    }
    void update (int node, int lb, int rb, int q_left, int q_right, int to_add) {
        if (q_left <= lb && rb <= q_right) {
            seg[node].value += to_add;
            lazy[node] += to_add;
            return;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        push (node);
        if (q_left <= mid)
            update (left_node, lb, mid, q_left, q_right, to_add);
        if (q_right >= mid + 1)
            update (right_node, mid + 1, rb, q_left, q_right, to_add);
        seg[node] = join (seg[left_node], seg[right_node]);
    }
    Node query (int node, int lb, int rb, int q_left, int q_right) {
        if (q_left > q_right)
            return {0, 0};
        if (q_left <= lb && rb <= q_right)
            return seg[node];
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        push (node);
        Node ans = {0, 0};
        if (q_left <= mid)
            ans = join (ans, query (left_node, lb, mid, q_left, q_right));
        if (q_right >= mid + 1)
            ans = join (ans, query (right_node, mid + 1, rb, q_left, q_right));
        return ans;
    }
};

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

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        gr[x].pb (y);
        gr[y].pb (x);
    }
    dfs_cycle (1, 0);
    for (int x : cycle)
        fix[x] = true;
    for (int x : cycle)
        dfs_depth (x, 0);
    vector <Node> elements;
    for (int x : cycle)
        elements.pb (max_depth[x]);
    for (int x : cycle)
        elements.pb (max_depth[x]);
    int m = cycle.size ();
    int sz = elements.size ();
    LazySegTree helper (sz);
    helper.build (1, 1, sz, elements);
    int from_right = m / 2;
    for (int i = 1; i <= m; i++) {
        Node ans_right = helper.query (1, 1, sz, i + 1, i + from_right);
        Node best = {ans_right.value + elements[i - 1].value, ans_right.cnt * elements[i - 1].cnt};
        ans = join (ans, best);
        helper.update (1, 1, sz, 1, i, 1);
        helper.update (1, 1, sz, i + 1, sz, -1);
    }
    cout << ans.cnt << "\n";
    return 0;
}

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