Submission #872078

#	Time	Username	Problem	Language	Result	Execution time	Memory
872078		vjudge1	Ball Machine (BOI13_ballmachine)	C++17	7.54 / 100	1092 ms	37464 KiB

ballmachine

/*              IN THE NAME OF GOD              */
// Oh, let the bullets fly, oh, let them rain
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100'000, lg = 18;

bool is_filled[MAXN + 10];
int par_sp[MAXN + 10][lg + 10], order[MAXN + 10], mn[MAXN + 10], par[MAXN + 10], n, q, tt;

vector<int> adj[MAXN + 10];
set<pair<int, int>> take_order;

void input();
void solve();
void dfs_get_minimum(int u, int par);
void dfs_get_order(int u, int par);
void par_spars_table();
int query1(int cnt);
int query2(int id);

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    input();
    solve();
    return 0;
}

void input() {
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> par[i];
        par[i]--;
        if (par[i] == -1)
            continue;
        adj[par[i]].push_back(i);
        adj[i].push_back(par[i]);
    }
}

void solve() {
    dfs_get_minimum(0, -1);
    dfs_get_order(0, -1);
    par_spars_table();
    //cout << par_sp[7][2] << '\n';
    for (int i = 0; i < n; i++)
        take_order.insert({order[i], i});
    while (q--) {
        int type, x;
        cin >> type >> x;
        if (type == 1)
            cout << query1(x) + 1 << '\n';
        else  {
            x--;
            cout << query2(x) << '\n';
        }
    }
}

void dfs_get_minimum(int u, int par) {
    int res = u;
    for (int v : adj[u])
        if (v != par) {
            dfs_get_minimum(v, u);
            res = min(res, mn[v]);
        }
    mn[u] = res;
}

void dfs_get_order(int u, int par) {
    set<pair<int, int>> st;
    for (int v : adj[u])
        if (v != par)
            st.insert({mn[v], v});
    for (auto p : st)
        dfs_get_order(p.second, u);
    order[u] = tt++;
}

void par_spars_table() {
    for (int i = 0; i < n; i++)
        par_sp[i][0] = par[i];
    for (int k = 1; k < lg; k++)
        for (int i = 0; i < n; i++) {
            if (par_sp[i][k - 1] == -1)
                par_sp[i][k] = -1;
        else
            par_sp[i][k] = par_sp[par_sp[i][k - 1]][k - 1];
        }
}

int query1(int cnt) {
    for (int i = 0; i < cnt; i++) {
        int u = (*take_order.begin()).second;
        is_filled[u] = true;
        take_order.erase(take_order.begin());
        if (i == cnt - 1)
            return u;
    }
}

int query2(int id) {
    int u = id, ans = 0;
    for (int k = lg - 1; k >= 0; k--) {
        if (par_sp[u][k] == -1)
            continue;
        if (is_filled[par_sp[u][k]] == true) {
            u = par_sp[u][k];
            ans += (1 << k);
        }
    }
    is_filled[u] = false;
    take_order.insert({order[u], u});
    return ans;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int query1(int)':
ballmachine.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
  100 | }
      | ^

• Subtask 1: 0 / 25
• Subtask 2: 6.428571428571429 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.1111111111111112 / 5