Submission #250719

#	Time	Username	Problem	Language	Result	Execution time	Memory
250719		Tc14	Ball Machine (BOI13_ballmachine)	C++17	79.52 / 100	1098 ms	34296 KiB

ballmachine

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
const int MAXN = 100000; 
const int L = 20;

int Root, HMax;
int M[MAXN], C[MAXN], H[MAXN], P[MAXN], A[MAXN][L];
bool U[MAXN];
ve<int> G[MAXN];
priority_queue<int, ve<int>, greater<int>> PQ[MAXN];

bool sortFunction(int a, int b) { return M[a] < M[b]; }

void dfs(int u) {

    int a, w;

    a = A[u][0];
    for (int i = 0; i < L; i++) {
        A[u][i] = a;
        if (a != -1) a = A[a][i]; 
    }

    M[u] = u;
    for (int v : G[u]) {
        dfs(v);
        M[u] = min(M[u], M[v]);
    }

    if (G[u].size() > 0) {
        sort(G[u].begin(), G[u].end(), sortFunction);
        for (int i = 0; i < G[u].size(); i++) {
            PQ[u].push(i);
            P[G[u][i]] = i;
        }
        w = G[u][0];
        if (H[w] == HMax) {
            C[u] = A[C[w]][0];
            H[u] = HMax;
        }
        else {
            C[u] = C[w];
            H[u] = H[w] + 1;
        }
    }
    else {
        C[u] = u;
        H[u] = 0;
    }
}

pii next(int u) {

    int h;

    h = 0;
    for (int i = 0; i < HMax; i++) {
        if (PQ[u].size() > 0) {
            u = G[u][PQ[u].top()];
            h++;
        }
        else break;
    }

    return {u, h};
}

int ins(int k) {

    int c, cNew, a, h;

    for (int i = 0; i < k; i++) {
        c = Root;
        while (c != C[c]) c = C[c];
        U[c] = true;
        a = A[c][0];
        if (a != -1) {
            PQ[a].pop();
            tie(cNew, h) = next(a);
            for (int j = 0; j < HMax; j++) {
                if (a != -1) {
                    C[a] = cNew;
                    a = A[a][0];
                    if (h == HMax) cNew = A[cNew][0];
                    else h++;
                }
                else break;
            }
        }
    }

    return c;
}

int del(int u) {

    int a, b, v, r;

    a = u;
    r = 0;
    for (int i = L - 1; i >= 0; i--) {
        if (A[a][i] != -1 && U[A[a][i]]) {
            r += 1 << i; 
            a = A[a][i];
        }
    }

    U[a] = false;
    b = A[a][0];
    if (b != -1) {
        PQ[b].push(P[a]);
        for (int j = 0; j < HMax; j++) {
            if (b != -1) {
                v = G[b][PQ[b].top()];
                if (C[v] == a) C[b] = a;
                else break;
                b = A[b][0];
            }
            else break;
        }
    }

    return r;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q, p, o, k, ans;

    cin >> n >> q;
    HMax = sqrt(n);

    for (int i = 0; i < n; i++) {
        cin >> p;
        p--;
        if (p != -1) G[p].push_back(i);
        else Root = i;
        A[i][0] = p;
    }

    dfs(Root);

    for (int i = 0; i < q; i++) {
        cin >> o >> k;
        if (o == 1) ans = ins(k) + 1;
        else ans = del(k - 1);
        cout << ans << "\n";
    }

    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:37:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < G[u].size(); i++) {
                         ~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int ins(int)':
ballmachine.cpp:97:12: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return c;
            ^

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