Submission #83244

#	Time	Username	Problem	Language	Result	Execution time	Memory
83244		teomrn	Ball Machine (BOI13_ballmachine)	C++14	42.88 / 100	985 ms	35452 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 inv ^ (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 && tata[where])
            free_nodes.push(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.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--) {
                    assert(!free_nodes.empty());
                    int q = free_nodes.top().nod;
                    free_nodes.pop();
                    while (nr_fii_activi[q] || taken[q]) {
                        assert(!free_nodes.empty());
                        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:115:33: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 cout << last << '\n';
                                 ^~~~
ballmachine.cpp:95:17: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
         RMQ::dfs(root, 0);
         ~~~~~~~~^~~~~~~~~

• Subtask 1: 1.9230769230769231 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 28.571428571428573 / 40
• Subtask 4: 1.6666666666666667 / 5