Submission #151935

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
151935	2019-09-05T14:44:53 Z	forestryks	Treasure Hunt (CEOI11_tre)	C++14	70 / 100	4000 ms	79832 KB

#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 back
        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;
    
}

int dig(int a, int b) {
    // dbg();s
    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;
        }
    }
    int lca = getup(ac, r);
    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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	504 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	632 KB	Output is correct
2	Correct	26 ms	888 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1817 ms	57704 KB	Output is correct

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	4093 ms	10720 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3227 ms	37200 KB	Output is correct
2	Correct	3978 ms	18936 KB	Output is correct

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	4096 ms	37436 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1908 ms	18844 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2847 ms	64720 KB	Output is correct
2	Correct	580 ms	79824 KB	Output is correct
3	Correct	517 ms	79832 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3984 ms	69120 KB	Output is correct

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	4099 ms	68336 KB	Time limit exceeded

Submission #151935

Compilation message