Submission #730432

#	Time	Username	Problem	Language	Result	Execution time	Memory
730432		thimote75	Ball Machine (BOI13_ballmachine)	C++14	97.14 / 100	1076 ms	38412 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<int>

vi parents;
gi parents_2k;
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 jump (int n, int k) {
    for (int i = 0; i < 20; i ++)
        if (n != -1 && (1 << i) & k)
            n = parents_2k[n][i];
    return n;
}

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

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

    parents_2k.resize(N, vi(20, -1));

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

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

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

    for (int k = 0; k + 1 < 20; k ++) {
        for (int i = 0; i < N; i ++) {
            if (parents_2k[i][k] == -1) continue ;

            parents_2k[i][k + 1]
             = parents_2k[parents_2k[i][k]][k];
        }
    }

    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]);

    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 << postorder[h] + 1 << endl;
            }
        } else {
            k --;
    
            int a = 0;
            int b = 1 << 20;
            while (b - a > 1) {
                int c = (a + b) >> 1;
                int m = jump(k, c);

                if (m == -1 || omega.find(rev_pord[m]) != omega.end())
                    b = c;
                else a = c;
            }

            int n = jump(k, a);
            omega.insert(rev_pord[n]);

            cout << a << endl;
        }
        
    }
}

Compilation message (stderr)

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

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