Submission #1243269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243269		julia_08	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	194 ms	31504 KiB

ballmachine

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

const int MAXN = 1e5 + 10;

int pre[MAXN], pos[MAXN];

int sub[MAXN], bit[MAXN];

int dp[20][MAXN];

vector<int> adj[MAXN];

set<pair<pair<int, int>, int>> empty_nodes;

int n;

bool cmp(int a, int b){
  return sub[a] < sub[b];
}

void bit_add(int pos, int x){
  for(int i=pos; i<=(n + 1); i+=(i&-i)){
    bit[i] += x;
  }
}

int bit_query(int pos){

  int sum = 0;

  for(int i=pos; i>0; i-=(i&-i)){
    sum += bit[i];
  } 

  return sum;

}

void dfs_0(int v){

  sub[v] = v;

  for(auto u : adj[v]){
    dfs_0(u);
    sub[v] = min(sub[v], sub[u]);
  }

}

int t = 0;

void dfs_1(int v){

  pre[v] = ++t;

  bit_add(pre[v], 1);

  for(auto u : adj[v]){
    dp[0][u] = v;
    dfs_1(u);
  }

  pos[v] = t;
  empty_nodes.insert({{pos[v], -pre[v]}, v});

}

pair<int, int> jump(int v){

  int d = 0;

  for(int k=19; k>=0; k--){
    if(bit_query(pos[dp[k][v]]) - bit_query(pre[dp[k][v]] - 1) == 0){
      d += (1 << k);
      v = dp[k][v];
    }
  }

  return {v, d};

}

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

  int q; cin >> n >> q;

  for(int i=1; i<=n; i++){
    int p; cin >> p;
    adj[p].push_back(i);
  }

  dfs_0(0);

  for(int i=1; i<=n; i++) sort(adj[i].begin(), adj[i].end(), cmp);

  dfs_1(0);

  for(int k=1; k<20; k++){
    for(int i=1; i<=n; i++){
      dp[k][i] = dp[k - 1][dp[k - 1][i]];
    }
  }

  while(q--){

    int type; cin >> type;

    if(type == 1){

      int k; cin >> k;

      int last = -1;

      while(k--){

        last = empty_nodes.begin()->second;

        bit_add(pre[last], -1);
        empty_nodes.erase(empty_nodes.begin());

      }

      cout << last << "\n";

    } else{

      int x; cin >> x;

      auto [v, d] = jump(x);
 
      empty_nodes.insert({{pos[v], -pre[v]}, v});
      bit_add(pre[v], 1);

      cout << d << "\n";

    }

  }

  return 0;
}

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