Submission #1094940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094940		gyg	Ball Machine (BOI13_ballmachine)	C++17	24.80 / 100	910 ms	29908 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vct vector
#define pii pair<int, int>
#define fir fir 
#define sec second 
const int MX_N = 1e5 + 5, INF = 1e9;

int n, q;
int rt;
arr<vct<int>, MX_N> chldrn;

int nm_inds;
arr<int, MX_N> ind, fn_ind, dpth;
arr<arr<int, 20>, MX_N> anc;
void dfs(int u = rt) {
    nm_inds++, ind[u] = nm_inds;
    for (int v : chldrn[u]) 
        dpth[v] = dpth[u] + 1, dfs(v), anc[v][0] = u;
    fn_ind[u] = nm_inds;
}

// bool is_anc(int u, int v) { return (ind[u] <= ind[v] && ind[v] <= fn_ind[u]); }
// int gt_anc(int u, int v) {
//     if (is_anc(u, v)) return u;
//     if (is_anc(v, u)) return v;
//     for (int i = 18; i >= 0; i--)
//         if (anc[u][i] != 0 && !is_anc(anc[u][i], v))
//             u = anc[u][i];
//     u = anc[u][0];
//     return u;
// }

arr<int, 4 * MX_N> sgtr;
void upd(bool is_mn, int i, int x, int u = 1, int lw = 1, int hg = n) {
    if (i < lw || hg < i) return;
    if (lw == hg) { sgtr[u] += x; return; }
    int md = (lw + hg) / 2;
    upd(is_mn, i, x, 2 * u, lw, md), upd(is_mn, i, x, 2 * u + 1, md + 1, hg);
    sgtr[u] = (is_mn) ? min(sgtr[2 * u], sgtr[2 * u + 1]) : sgtr[2 * u] + sgtr[2 * u + 1];
}
int qry(bool is_mn, int l, int r, int u = 1, int lw = 1, int hg = n) {
    if (l > r) return INF;
    if (r < lw || hg < l) return ((is_mn) ? INF : 0);
    if (l <= lw && hg <= r) return sgtr[u];
    int md = (lw + hg) / 2;
    if (is_mn) return min(qry(is_mn, l, r, 2 * u, lw, md), qry(is_mn, l, r, 2 * u + 1, md + 1, hg));
    return qry(is_mn, l, r, 2 * u, lw, md) + qry(is_mn, l, r, 2 * u + 1, md + 1, hg);
}

vct<int> ord;
void mk_ord(int u = 0) {
    while (true) {
        int v = qry(true, ind[u] + 1, fn_ind[u]);
        if (v >= INF) break;
        mk_ord(v);
    }
    if (u == 0) return;
    ord.push_back(u);
    upd(true, ind[u], INF);
}
arr<int, MX_N> scr;

set<pii> offs;
void trn_on(int u) {
    offs.erase({scr[u], u});
    upd(false, ind[u], -1), upd(false, fn_ind[u] + 1, +1);
}
void trn_off(int u) {
    offs.insert({scr[u], u});
    upd(false, ind[u], +1), upd(false, fn_ind[u] + 1, -1);
}

void prcmp() {
    dfs();

    for (int i = 1; i <= 18; i++)
        for (int u = 1; u <= n; u++)
            anc[u][i] = anc[anc[u][i - 1]][i - 1];

    for (int u = 1; u <= n; u++) upd(true, ind[u], u);
    ind[0] = 0, fn_ind[0] = n;
    mk_ord();
    for (int i = 0; i < n; i++) scr[ord[i]] = i + 1;
    
    fill(sgtr.begin(), sgtr.end(), 0);
    for (int u = 1; u <= n; u++) trn_off(u);

    // for (int u : ord) cout << u << " ";
    // cout << endl;
}   

int ins() {
    int u = offs.begin()->sec; 
    trn_on(u);
    return u;
}
int qry_pth(int u, int v) {
    if (u == rt) return qry(false, 1, ind[v]);
    return qry(false, 1, ind[v]) - qry(false, 1, ind[anc[u][0]]);
}
int hghst(int u) {
    int v = u;
    for (int i = 18; i >= 0; i--)
        if (anc[v][i] != 0 && qry_pth(anc[v][i], u) == 0)
            v = anc[v][i];
    return v;
}
int dlt(int u) {
    int v = hghst(u);
    trn_off(v);
    return dpth[u] - dpth[v];
}

int main() {
    // freopen("bll.in", "r", stdin);
    cin >> n >> q;
    for (int u = 1; u <= n; u++) {
        int pr; cin >> pr;
        if (pr == 0) rt = u;
        else chldrn[pr].push_back(u);
    }

    prcmp();
    for (int i = 1; i <= q; i++) {
        int typ, x; cin >> typ >> x;
        int ans = -1;
        if (typ == 1) {
            for (int j = 1; j <= x; j++) ans = ins();
        } else {
            ans = dlt(x);
        }
        cout << ans << endl;

        // cout << "DEBUG: ";
        // for (pii y : offs)
        //     cout << y.sec << " ";
        // cout << endl;
    }

}

• Subtask 1: 3.8461538461538463 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 1.6666666666666667 / 5