Submission #520119

#	Time	Username	Problem	Language	Result	Execution time	Memory
520119		arnav2004	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	212 ms	37004 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int LOG = 25;
int N,Q;
int subtree[100005];
vector<int> graph[100005];
int post[100005];
int depth[100005];
bool filled[100005];
int up[100005][LOG];
int timer = 0;
struct cmp{
  bool operator()(const int &a, const int &b){
    return post[a] > post[b];
  }
};
void dfs(int node, int par){
  subtree[node] = node;
  for(int v : graph[node]){
    if(v == par) continue;
    up[v][0] = node;
    depth[v] = depth[node] + 1;
    dfs(v, node);
    subtree[node] = min(subtree[node], subtree[v]);
  }
}
void post_order(int node, int par){
  for(int v : graph[node]){
    if(v != par)
      post_order(v, node);
  }
  post[node] = timer++;
}
void binary_lift(int node, int par){
  for(int j = 1; j < LOG; j++){
    for(int i = 0; i < N; i++)
      up[i][j] = up[up[i][j - 1]][j - 1];
  }
}
signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> Q;
  int root = -1;
  for(int i = 0; i < N; i++){
    subtree[i] = 100005;
    int x; cin >> x;
    x--;
    if(x == -1) root = i;
    else{
      graph[x].emplace_back(i);
      graph[i].emplace_back(x);
    }
  }
  assert(root != -1);
  depth[root] = 0;
  dfs(root, -1);
  up[root][0] = root;
  for(int i = 0; i < N; i++){
    sort(graph[i].begin(), graph[i].end(), [&](const int &x, const int &y){
      return subtree[x] < subtree[y];
    });
  }
  binary_lift(root, -1);
  post_order(root, -1);
  priority_queue<int, vector<int>, cmp> khaali;
  for(int i = 0; i < N; i++)
    khaali.push(i);
  while(Q--){
    int T,K; cin >> T >> K;
    if(T == 1){
      for(int j = 0; j < K; j++){
        int x = khaali.top();
        khaali.pop();
        filled[x] = true;
        if(j == K - 1) cout << x + 1 << '\n';
      }
    }
    else{
      K--;
      int pos = K;
      for(int i = LOG - 1; i >= 0; i--){
        if(filled[up[pos][i]])
        pos = up[pos][i];
      }
      filled[pos] = false;
      khaali.push(pos);
      cout << depth[K] - depth[pos] << '\n';
    }
  }
  return 0;
} 

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