Submission #83248

#	Time	Username	Problem	Language	Result	Execution time	Memory
83248		teomrn	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	238 ms	28576 KiB

ballmachine

#include <bits/stdc++.h>
#define lsb(x) ((x) & -(x))
using namespace std;

const int NMAX = 100010;
const int LGMAX = 18;

vector <int> adia[NMAX + 10];
bool taken[NMAX + 10];
int tata[NMAX + 10];
int stramos[LGMAX + 1][NMAX + 10];
int vmin[NMAX + 10];
int aib[NMAX + 10];
int poz[NMAX + 10];
int is_on_poz[NMAX + 10], naib, cnt;

void update(int poz, int val)
{
    while (poz <= naib)
        aib[poz] += val, poz += lsb(poz);
}

int first_empty()
{
    int ans = 0, pas = 2 * naib;
    while (pas /= 2)
        if (aib[ans + pas] == pas)
            ans += pas;
    return ans + 1;
}

void dfs(int nod, int tata) {
    vmin[nod] = nod;
    stramos[0][nod] = tata;
    for (int i = 1; i <= LGMAX; i++)
        stramos[i][nod] = stramos[i - 1][stramos[i - 1][nod]];
    for (auto i : adia[nod]) {
        dfs(i, nod);
        vmin[nod] = min(vmin[nod], vmin[i]);
    }
}

void dfs2(int nod)
{
    sort(adia[nod].begin(), adia[nod].end(), [](int a, int b) { return vmin[a] < vmin[b]; });
    for (auto i : adia[nod])
        dfs2(i);
    poz[nod] = ++cnt;
    is_on_poz[cnt] = nod;
}

int add()
{
    int where = first_empty();
    update(where, 1);
    taken[is_on_poz[where]] = 1;
    return is_on_poz[where];
}

int rem(int where)
{
    assert(taken[where]);
    int ans = 0;
    for (int i = LGMAX; i >= 0; i--)
        if (taken[stramos[i][where]])
            ans += (1 << i), where = stramos[i][where];

    taken[where] = 0;
    update(poz[where], -1);
    return ans;
}

int main()
{
    int n, m;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    int root;
    naib = n;
    while (naib != lsb(naib))
        naib += lsb(naib);

    for (int i = 1; i <= n; i++) {
        cin >> tata[i];
        if (tata[i] == 0)
            root = i;
        adia[tata[i]].push_back(i);
    }

    dfs(root, 0);
    dfs2(root);

    while (m--) {
        int type, x;
        cin >> type >> x;

        if (type == 1) {
            int last;
            while (x--)
                last = add();

            cout << last << '\n';
        }
        else
            cout << rem(x) << '\n';
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:103:29: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout << last << '\n';
                             ^~~~
ballmachine.cpp:92:9: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs2(root);
     ~~~~^~~~~~

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