Submission #102187

#	Time	Username	Problem	Language	Result	Execution time	Memory
102187		WLZ	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	504 ms	35320 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
 
vector<int> p, order, depth, pos, used, mn;
vector< vector<int> > children, up;
int root, cnt, max_log;
 
void dfs(int u, int par, int d) {
  mn[u] = u;
  depth[u] = d;
  vector< pair<int, vector<int> > > tmp;
  up[u][0] = par;
  for (int i = 1; i <= max_log; i++) {
    up[u][i] = up[up[u][i - 1]][i - 1];
  }
  for (auto v : children[u]) {
    dfs(v, u, d + 1);
    mn[u] = min(mn[u], mn[v]);
  }
}

void preorder(int u) {
  priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
  for (auto& v : children[u]) {
    pq.push({mn[v], v});
  }
  while (!pq.empty()) {
    preorder(pq.top().second);
    pq.pop();
  }
  order.push_back(u);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  max_log = (int) ceil(log2((double) n));
  up.assign(n + 1, vector<int>(max_log + 1));
  p.resize(n + 1);
  children.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    if (p[i] == 0) {
      root = i;
    } else {
      children[p[i]].push_back(i);
    }
  }
  depth.resize(n + 1);
  pos.resize(n + 1);
  mn.resize(n + 1);
  dfs(root, root, 0);
  preorder(root);
  for (int i = 0; i < n; i++) {
    pos[order[i]] = i;
  }
  used.assign(n + 1, 0);
  set<int> st;
  for (int i = 1; i <= n; i++) {
    st.insert(pos[i]);
  }
  while (q--) {
    int type, k;
    cin >> type >> k;
    if (type == 1) {
      int last;
      set<int> newSt;
      for (auto& x : st) {
        k--;
        used[order[x]] = 1;
        last = order[x];
        st.erase(x);  
        if (k == 0) {
          cout << last << '\n';
          break;
        }
      }
    } else {
      int oldK = k;
      for (int i = max_log; i >= 0; i--) {
        if (used[up[k][i]]) {
          k = up[k][i];
        }
      }
      used[k] = 0;
      st.insert(pos[k]);
      cout << depth[oldK] - depth[k] << '\n';
    }
  }
  return 0;
}

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