Submission #730427

#	Time	Username	Problem	Language	Result	Execution time	Memory
730427		thimote75	Ball Machine (BOI13_ballmachine)	C++14	60.08 / 100	1091 ms	26472 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define gi vector<vi>
#define pq priority_queue<pair<int, int>>
#define sq set<pair<int, int>>

vi parents;
gi roads;
vi postorder;
vi rev_pord;
vi subtree;
sq omega;

int init_ddfs ( int node, int parent ) {
    int min_s = node;
    pq rebase;

    for (int next : roads[node]) {
        int loc_s = init_ddfs(next, node);
        rebase.push({ - loc_s, next });
        min_s = min(min_s, loc_s);
    }

    roads[node].clear();
    while (rebase.size() != 0) {
        auto u = rebase.top(); rebase.pop();

        roads[node].push_back(u.second);
    }

    return min_s;
}
int dfs (int node, int parent) {
    subtree[node] = 1;
    for (int next : roads[node])
        subtree[node] += dfs(next, node);
    
    postorder.push_back(node);
    return subtree[node];
}

int main () {
    int N, Q;
    cin >> N >> Q;

    int root;
    parents.resize(N);
    roads  .resize(N);
    subtree.resize(N);

    for (int i = 0; i < N; i ++) {
        cin >> parents[i]; parents[i] --;

        if (parents[i] == -1) root = i;
        else {
            roads[parents[i]].push_back(i);
        }
    }

    init_ddfs(root, -1);
    dfs(root, -1);

    rev_pord.resize(N);
    for (int i = 0; i < N; i ++)
        rev_pord[postorder[i]] = i;
    for (int i = 0; i < N; i ++)
        omega.insert({ rev_pord[i], i });

    for (int q = 0; q < Q; q ++) {
        int t, k;
        cin >> t >> k;

        if (t == 1) {
            for (int _k = k - 1; _k >= 0; _k --) {
                auto h = *omega.begin();
                omega.erase(h);

                if (_k == 0)
                    cout << h.second + 1 << endl;
            }
        } else {
            k --;

            int i = 0;
            while (parents[k] != -1 && omega.find({ rev_pord[parents[k]], parents[k] }) == omega.end()) {
                k = parents[k];
                i ++;
            }
            omega.insert({ rev_pord[k], k });

            cout << i << endl;
        }
        
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:65:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |     dfs(root, -1);
      |     ~~~^~~~~~~~~~

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