Submission #666880

#	Time	Username	Problem	Language	Result	Execution time	Memory
666880		definitelynotmee	Ball Machine (BOI13_ballmachine)	C++98	100 / 100	138 ms	20928 KiB

ballmachine

#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

struct lift{
    int pai, d, jmp;
};


int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    cin >> n >> q;

    vector<int> pai(n+1);
    int root = 0;

    matrix<int> g(n+1);

    for(int i = 1; i <= n; i++){
        cin >> pai[i];
        if(pai[i]!=0){
            g[pai[i]].push_back(i);
        } else root = i;
    }

    vector<int> mn(n+1,1e9);
    auto prec=[&](int id, auto dfs)->void{
        mn[id] = id;
        for(int i : g[id]){
            dfs(i,dfs);
            mn[id] = min(mn[id],mn[i]);
        }
        sort(all(g[id]),[&](int a, int b){
            return mn[a] < mn[b];
        });
    };
    prec(root,prec);

    priority_queue<pii,vector<pii>,greater<pii>> pq;

    int timer = -1;

    vector<int> order(n+1), taken(n+1);

    vector<lift> trick(n+1);
    trick[root] = {root,0,root};

    auto append =[&](int f){
        trick[f].pai = pai[f];
        trick[f].d = 1;
        trick[f].jmp = pai[f];
        while(trick[trick[f].jmp].d == trick[f].d){
            trick[f].d*=2;
            trick[f].jmp = trick[trick[f].jmp].jmp;
        }
    };

    auto dfs=[&](int id, auto dfs)->void{
        for(int i : g[id]){
            append(i);
            dfs(i,dfs);
        }
        order[id] = ++timer;
        pq.push({order[id],id});
    };
    dfs(root,dfs);

    while(q--){
        int type, x;
        cin >> type >> x;
        if(type == 1){
            int cur;
            while(x--){
                cur = pq.top().ss;
                taken[cur] = 1;
                pq.pop();
            }
            cout << cur << '\n';
        } else {
            int ct = 0;
            while(taken[pai[x]]){
                if(taken[trick[x].jmp])
                    ct+=trick[x].d, x = trick[x].jmp;
                else ct++, x = trick[x].pai;
            }
            pq.push({order[x],x});
            taken[x] = 0;
            cout  << ct << '\n';
        }
    }

}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:87:28: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |             cout << cur << '\n';
      |                            ^~~~

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