Submission #666855

#	Time	Username	Problem	Language	Result	Execution time	Memory
666855		definitelynotmee	Ball Machine (BOI13_ballmachine)	C++98	16.23 / 100	127 ms	18604 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>>;

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);
            pai[i] = 0;
        } 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);

    auto dfs=[&](int id, auto dfs)->void{

        for(int i : g[id]){
            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;
                pq.pop();
                for(int i : g[cur])
                    pai[i] = cur;
            }
            cout << cur << '\n';
        } else {
            int ct = -1;
            while(x){
                pq.push({order[x],x});
                int tmp = pai[x];
                pai[x] = 0;
                ct++;
                x = tmp;
            }
            cout << ct << '\n';
        }
    }

}

Compilation message (stderr)

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

• Subtask 1: 3.8461538461538463 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.6666666666666667 / 5