Submission #83242

#	Time	Username	Problem	Language	Result	Execution time	Memory
83242		teomrn	Ball Machine (BOI13_ballmachine)	C++14	48.04 / 100	1089 ms	23740 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) {
        int inv = 0;
        if (h[a] < h[b])
            swap(a, b), inv = 1;
        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]) ^ inv;
    }
}

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

set <Node> free_nodes;

void add(int where)
{
    free_nodes.erase(where);
    assert(nr_fii_activi[where] == 0 && !taken[where]);
    taken[where] = 1;
    nr_fii_activi[tata[where]]--;
    if (nr_fii_activi[tata[where]] == 0 && tata[where])
        free_nodes.insert(tata[where]);
}

int rem(int where)
{
    assert(taken[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.erase(tata[where]);
    free_nodes.insert(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]]++;
    }

    RMQ::dfs(root, 0);

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



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

        if (type == 1) {
            int last;
            while (x--) {
                assert(!free_nodes.empty());
                int q = free_nodes.begin()->nod;

                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:116:29: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout << last << '\n';
                             ^~~~
ballmachine.cpp:95:13: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     RMQ::dfs(root, 0);
     ~~~~~~~~^~~~~~~~~

• Subtask 1: 19.23076923076923 / 25
• Subtask 2: 12.857142857142858 / 30
• Subtask 3: 14.285714285714286 / 40
• Subtask 4: 1.6666666666666667 / 5