Submission #666838

#	Time	Username	Problem	Language	Result	Execution time	Memory
666838		pedroslrey	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	385 ms	23484 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;
const int MAXK = 20;

vector<int> graph[MAXN];
int dp[MAXN][MAXK], prof[MAXN], mn[MAXN], xs[MAXN], redro[MAXN];
vector<int> order;
int seg[4*MAXN];

void dfs1(int u) {
    mn[u] = u;
    for (int v: graph[u]) {
        dfs1(v);
        mn[u] = min(mn[u], mn[v]);
    }
}

void dfs2(int u) {
    sort(graph[u].begin(), graph[u].end(), [&](int a, int b) { return mn[a] < mn[b]; });
    for (int v: graph[u]) {
        prof[v] = prof[u] + 1;
        dp[v][0] = u;
        for (int k = 1; k < MAXK; ++k)
            dp[v][k] = dp[dp[v][k-1]][k-1];
        dfs2(v);
    }
    redro[u] = order.size();
    order.push_back(u);
}

void update(int pos, int ini, int fim, int idx, int x) {
    if (ini == fim) {
        seg[pos] = x;
        return;
    }

    int m = (ini + fim)/2;
    if (idx <= m) update(2*pos, ini, m, idx, x);
    else update(2*pos + 1, m + 1, fim, idx, x);

    seg[pos] = min(seg[2*pos], seg[2*pos + 1]);
}

int bsearch(int pos, int ini, int fim) {
    if (ini == fim) return ini;

    int m = (ini + fim)/2;
    if (!seg[2*pos]) return bsearch(2*pos, ini, m);
    return bsearch(2*pos + 1, m + 1, fim);
}

int main() {
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;

        graph[x].push_back(i);
    }

    dfs1(0);
    dfs2(0);

    for (int qq = 0; qq < q; ++qq) {
        int t, x;
        cin >> t >> x;

        if (t == 1) {
            int pos;
            for (int i = 0; i < x; ++i) {
                pos = bsearch(1, 0, n);
                update(1, 0, n, pos, 1);
                xs[order[pos]] = 1;
            }
            cout << order[pos] << "\n";
        }
        else {
            int atual = x;
            for (int k = MAXK-1; k >= 0; --k)
                if (xs[dp[atual][k]]) atual = dp[atual][k];
            update(1, 0, n, redro[atual], 0);
            xs[atual] = 0;

            cout << prof[x] - prof[atual] << "\n";
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:80:30: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |             cout << order[pos] << "\n";
      |                              ^

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