Submission #151945

#	Time	Username	Problem	Language	Result	Execution time	Memory
151945		forestryks	Treasure Hunt (CEOI11_tre)	C++14	100 / 100	3961 ms	70192 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define f first
#define s second

const int MAXN = 1e6 + 5;
int n = 1;
int last = 1;
bool pe[MAXN];
int p[MAXN];
int up[MAXN][21];
int pval[MAXN];
pair<int, int> e[MAXN];
map<pair<int, int>, int> seg;
int h[MAXN];
int realh[MAXN];

void build_up(int v) {
    up[v][0] = p[v];
    for (int i = 1; i < 21; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
}

int get_node(int a) {
    return prev(seg.upper_bound({a, 2e9}))->s;
}

int get_realh(int a) {
    int v = get_node(a);
    // cout << "gr " << a << " = " << realh[v] - (e[v].s - a) << endl;
    return realh[v] - (e[v].s - a);
}

void init() {
    // val[0] = 0;
    p[0] = 0;
    build_up(0);
    e[0] = {0, 0};
    seg[e[0]] = 0;
    h[0] = 0;
    realh[0] = 1;
}

void dbg() {
    rep(i, n) {
        cout << "node " << i << endl;
        cout << "p " << p[i] << endl;
        cout << "pval " << pval[i] << endl;
        cout << "h " << h[i] << endl;
        cout << "realh " << realh[i] << endl;
        cout << "seg " << e[i].f << ' ' << e[i].s << endl;
        cout << endl;
    }
}

void path(int a, int s) {
    a--;
    int v = get_node(a);

    // cout << " : " << v << endl;

    if (a == e[v].s) {
        // cout << "exp" << endl;
        // explicit parent, no need to create extra node
        pe[n] = true;
        p[n] = v;
        build_up(n);
        pval[n] = a;
        e[n] = {last, last + s - 1};
        seg[e[n]] = n;
        h[n] = h[v] + 1;
        realh[n] = realh[v] + s;
        last += s;
        n++;
    } else {
        // cout << "imp" << endl;
        // create extra node
        pe[n] = false;
        p[n] = p[v];
        build_up(n);
        pval[n] = a;
        e[n] = {last, last};
        seg[e[n]] = n;
        h[n] = h[v];
        realh[n] = get_realh(a) + 1;
        last++;
        n++;

        a = last; // in call to path() will be decreased
        s--;
        if (s > 0) {
            path(a, s);
            return;
        }
    }
    // dbg();
}

int fgetup(int a, int x, int v, int h) {
    int tarh = h - x;
    for (int i = 20; i >= 0; --i) {
        if (realh[up[v][i]] >= tarh) {
            v = up[v][i];
            // cout << " -- " << i << ' ' << v << endl;
        }
    }
    if (pe[v] || tarh == realh[v]) {
        return e[v].s - (realh[v] - tarh);
    } else {
        return pval[v] - (realh[v] - tarh - 1);
    }
}

int getup(int a, int x) {
    // cout << "getup " << a << ' ' << x << endl;
    int v = get_node(a);
    int h = get_realh(a);
    // cout << get_realh(a) << endl;
    // cout << v << ' ' << tarh << endl;
    return fgetup(a, x, v, h);
    // cout << " : " << v << endl;
    
}

void align(int &a, int &b) {
    int ah = get_realh(a), bh = get_realh(b);
    if (ah > bh) {
        a = getup(a, ah - bh);
    } else {
        b = getup(b, bh - ah);
    }
}

void align_vertex(int &v1, int &v2) {
    for (int i = 20; i >= 0; --i) {
        if (h[up[v1][i]] >= h[v2]) {
            v1 = up[v1][i];
        }
    }
}

int find_lca(int a, int b) {
    // cout << "find_lca " << a << ' ' << b << endl;
    align(a, b);
    if (a == b) return a;

    // cout << "aligned " << a << ' ' << b << endl;

    // now they are definitely on different explicit edges and neither of them is parent of another
    int v1 = get_node(a), v2 = get_node(b);

    // cout << v1 << ' ' << v2 << endl;

    align_vertex(v1, v2);
    align_vertex(v2, v1);

    // cout << v1 << ' ' << v2 << endl;

    for (int i = 20; i >= 0; --i) {
        if (up[v1][i] != up[v2][i]) {
            v1 = up[v1][i];
            v2 = up[v2][i];
        }
    }

    // cout << v1 << ' ' << v2 << endl;

    if (pe[v1] && pe[v2]) {
        assert(p[v1] == p[v2]);
        return e[p[v1]].s;
    }

    // a = e[v1].s, b = e[v2].s;

    assert(p[v1] == p[v2]);

    if (pe[v1]) {
        a = e[v1].s;
    } else {
        a = pval[v1];
    }

    if (pe[v2]) {
        b = e[v2].s;
    } else {
        b = pval[v2];
    }

    // // cout << a << ' ' << b << endl;

    // return min(a, b);




    int ac = a, bc = b;
    int h1 = get_realh(ac), h2 = get_realh(bc);
    if (h1 > h2) {
        ac = getup(ac, h1 - h2);
    } else {
        bc = getup(bc, h2 - h1);
    }

    // cout << ac << ' ' << bc << endl;

    int av = get_node(ac), ah = get_realh(ac), bv = get_node(bc), bh = get_realh(bc);

    int l = -1, r = 1e9 + 8;
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if (fgetup(ac, m, av, ah) == fgetup(bc, m, bv, bh)) {
            r = m;
        } else {
            l = m;
        }
    }

    return getup(ac, r);
}

int dig(int a, int b) {
    a--; b--;
    // dbg();

    // int ac = a, bc = b;
    // int h1 = get_realh(ac), h2 = get_realh(bc);
    // if (h1 > h2) {
    //     ac = getup(ac, h1 - h2);
    // } else {
    //     bc = getup(bc, h2 - h1);
    // }

    // // cout << ac << ' ' << bc << endl;

    // int av = get_node(ac), ah = get_realh(ac), bv = get_node(bc), bh = get_realh(bc);

    // int l = -1, r = 1e9 + 8;
    // while (r - l > 1) {
    //     int m = l + (r - l) / 2;
    //     if (fgetup(ac, m, av, ah) == fgetup(bc, m, bv, bh)) {
    //         r = m;
    //     } else {
    //         l = m;
    //     }
    // }

    int lca = find_lca(a, b);

    int lch = get_realh(lca);

    int uh = get_realh(a), vh = get_realh(b);
    int d = uh + vh - 2 * lch;
    int da = d / 2;
    if (uh >= vh) {
        return getup(a, da) + 1;
    } else {
        return getup(b, d - da) + 1;
    }

    // int u0 = get_node(a), v0 = get_node(b);
    // int u = u0, v = v0;

    // for (int i = 20; i >= 0; --i) {
    //     if (h[up[u][i]] <= h[v]) {
    //         u = up[u][i];
    //     }
    // }

    // for (int i = 20; i >= 0; --i) {
    //     if (h[up[v][i]] <= h[u]) {
    //         v = up[v][i];
    //     }
    // }

    // if (u == v) {
    //     // one of nodes is parent of other
    //     int uh = get_realh(u), vh = get_realh(v);
    //     if (uh > )
    // }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10