Submission #730422

#	Time	Username	Problem	Language	Result	Execution time	Memory
730422		thimote75	Ball Machine (BOI13_ballmachine)	C++14	60.08 / 100	1083 ms	23076 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

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

vi parents;
gi roads;
vi postorder;
vi subtree;
vi 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);

    omega.resize(N);

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

        if (t == 1) {
            for (int i = 0; i < N && k != 0; i ++) {
                if (omega[postorder[i]] == 0) {
                    omega[postorder[i]]  = 1;

                    k --;
                    if (k == 0)
                        cout << postorder[i] + 1 << endl;
                }
            }
        } else {
            k --;

            int i = 0;
            while (parents[k] != -1 && omega[parents[k]] == 1) {
                k = parents[k];
                i ++;
            }
            omega[k] = 0;

            cout << i << endl;
        }
        
    }
}

Compilation message (stderr)

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

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