Submission #83233

#	Time	Username	Problem	Language	Result	Execution time	Memory
83233		teomrn	Ball Machine (BOI13_ballmachine)	C++14	20.40 / 100	1082 ms	21328 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

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

vector <int> adia[NMAX + 10];
int nr_fii_activi[NMAX + 10];
bool taken[NMAX + 10];
int tata[NMAX + 10];

namespace RMQ {
    int h[NMAX + 10];
    int stramos[LGMAX + 1][NMAX + 10];
    int vmin[NMAX + 10];

    void dfs(int nod, int tata) {
        h[nod] = 1 + h[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]);
        }
    }

    bool mai_mic(int a, int b) {
        if (h[a] < h[b])
            swap(a, b);
        for (int i = LGMAX; i >= 0; i--)
            if (h[a] - (1 << i) >= h[b])
                a = stramos[i][a];
        for (int i = LGMAX; i >= 0; i--)
            if (stramos[i][a] != stramos[i][b])
                a = stramos[i][a], b = stramos[i][b];
        return vmin[a] < vmin[b];
    }
}

struct Node {
    Node(int x) : nod(x) { }
    int nod;
    bool operator< (const Node & n) const {
        return RMQ::mai_mic(n.nod, nod);
    }
};

priority_queue <Node> free_nodes;

void add(int where)
{
    taken[where] = 1;
    nr_fii_activi[tata[where]]--;
    if (nr_fii_activi[tata[where]] == 0)
        free_nodes.push(tata[where]);
}

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

    taken[where] = 0;
    nr_fii_activi[tata[where]]++;
    free_nodes.push(where);
    return ans;
}

int main()
{
    int n, m;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    int root;

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

    for (int i = 1; i <= n; i++)
        if (nr_fii_activi[i] == 0)
            free_nodes.push(i);

    RMQ::dfs(root, 0);

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

        if (type == 1) {
            int last;
            while (x--) {
                int q = free_nodes.top().nod;
                free_nodes.pop();
                while (nr_fii_activi[q] || taken[q]) {
                    q = free_nodes.top().nod;
                    free_nodes.pop();
                }
                last = q;
                add(q);
            }
            cout << last << '\n';
        }
        else
            cout << rem(x) << '\n';
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:111:29: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout << last << '\n';
                             ^~~~
ballmachine.cpp:93:13: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     RMQ::dfs(root, 0);
     ~~~~~~~~^~~~~~~~~

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