Submission #1211567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211567		i_love_spring	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	282 ms	27384 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int N = 1e5+5,LGN = 18;
int n,r,q,p[N],mn[N],ord[N],have[N],lift[N][LGN];
set<ar<int,2>> order;
vector<int>adj[N];
void dfs(int u,int p) {
  if(adj[u].empty()) mn[u] = u;
  for (int v : adj[u]) {
    if (v == p) continue;
    dfs(v,u);
    mn[u] = min(mn[u],mn[v]);
  }
}
void dfs2(int u,int p) {
  for (int v : adj[u]) {
    if (v == p) continue;
    dfs2(v,u);
  }
  ord[u] = (int)order.size() + 1;
  order.insert({ord[u],u});
}
void build(){
  for (int i = 0; i <= n;i++) {
    lift[i][0] = p[i];
  }
  for (int lg = 1; lg < LGN;lg++) {
    for (int i = 0; i <= n;i++) {
      lift[i][lg] = lift[lift[i][lg - 1]][lg - 1];
    }
  }
}
int get_kth(int u, int k) {
  int ans = u;
  for (int i = LGN - 1; i >= 0;i--) {
    if (k & (1 << i)) {
      ans = lift[ans][i];
    }
  }
  return ans;
}
bool check(int u,int x) {
  return have[get_kth(u,x)];
}
void solve() {  
  cin >> n >> q;
  for (int i = 0; i < n;i++) mn[i] = i, have[i] = 0;
  for (int i = 0; i < n;i++) {
    cin >> p[i],--p[i];
    if (p[i] == -1) {
      r = i;
      p[i] = n;
      p[n] = n;
      have[n] = 0;
      continue;
    }
    adj[p[i]].push_back(i);
  } 
  dfs(r,r);
  for (int i = 0; i < n;i++) {
    sort(adj[i].begin(),adj[i].end(),[&](int x,int y) {
      return mn[x] < mn[y];
    });
  }
  dfs2(r,r);
  build();
  while(q--) {
    int qt,k;
    cin >> qt >> k;
    if (qt == 1) {
      for (int i= 0; i < k - 1;i++) {
        have[(*order.begin())[1]] = 1;
        order.erase(order.begin());
      }
      have[(*order.begin())[1]] = 1;
      cout << (*order.begin())[1] + 1 << "\n";
      order.erase(order.begin());
    }else {
      --k;
      int L = 0, R = n, ans = 0;
      while (L <= R) {
        int M = (L + R) / 2;
        if (check(k,M)) L = M + 1,ans = M;
        else R = M - 1;
      }
      int pr = get_kth(k,ans);
      order.insert({ord[pr],pr});
      have[pr] = 0;
      cout << ans << "\n";
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
 // cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  return 0;
} 

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