Submission #385925

#	Time	Username	Problem	Language	Result	Execution time	Memory
385925		Aryan_Raina	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	346 ms	33892 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define ar array

const int INF = 1e15;
const int MOD = 1e9+7;

const int MXN = 1e5+9;
int up[20][MXN], mn[MXN], dist[MXN], ind[MXN];
vector<int> order, g[MXN];
bool hasBoulder[MXN];

void get_dp(int u) {
    mn[u] = u;
    for (int v : g[u]) {
        dist[v] = dist[u] + 1;
        get_dp(v);
        mn[u] = min(mn[u], mn[v]);
    }
}

void get_order(int u) {
    sort(g[u].begin(), g[u].end(), [&](int i, int j) { return mn[i] < mn[j]; });
    for (int v : g[u]) get_order(v);
    ind[u] = order.size();
    order.push_back(u);
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, rt; cin>>n>>m;
    for (int i = 0; i < n; i++) {
        cin>>up[0][i]; up[0][i]--;
        if (up[0][i] >= 0) g[up[0][i]].push_back(i);
        else up[0][i] = rt = i;
    }

    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            up[i][j] = up[i-1][up[i-1][j]];
        }
    }

    get_dp(rt);
    get_order(rt);

    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i++) pq.push(i);
    while (m--) {
        int t, x, ans; cin>>t>>x;
        if (t == 1) {
            while (x--) {
                hasBoulder[order[pq.top()]] = 1;
                ans = order[pq.top()]; pq.pop();
            }
            cout<<ans+1<<"\n";
        } else {
            x--;
            ans = dist[x];
            for (int i = 19; i >= 0; i--) {
                if (hasBoulder[up[i][x]]) x = up[i][x];
            }
            hasBoulder[x] = 0;
            pq.push(ind[x]);
            cout<<ans - dist[x]<<"\n";
        }
    }
}  

Compilation message (stderr)

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:59:23: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |             cout<<ans+1<<"\n";
      |                       ^
ballmachine.cpp:48:14: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     get_order(rt);
      |     ~~~~~~~~~^~~~

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