Submission #102179

#	Time	Username	Problem	Language	Result	Execution time	Memory
102179		WLZ	Ball Machine (BOI13_ballmachine)	C++17	13.46 / 100	1086 ms	23500 KiB

ballmachine

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

vector<int> p, order;
vector< vector<int> > children;
vector<int> used;
int root, cnt;

pair<int, vector<int> > dfs(int u) {
  int mn = u;
  vector< pair<int, vector<int> > > tmp;
  for (auto v : children[u]) {
    tmp.push_back(dfs(v));
    mn = min(mn, tmp.back().first);
  }
  sort(tmp.begin(), tmp.end());
  vector<int> ans;
  for (auto& v : tmp) {
    for (auto& x : v.second) {
      ans.push_back(x);
    }
  }
  ans.push_back(u);
  return {mn, ans};
}

void remove(int u) {
  for (auto& v : children[u]) {
    remove(v);
  }
  if (!used[u] && used[p[u]]) {
    swap(used[u], used[p[u]]);
    cnt++;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  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);
    }
  }
  order = dfs(root).second;
  used.assign(n + 1, 0);
  while (q--) {
    int type, k;
    cin >> type >> k;
    if (type == 1) {
      int last = 0;
      for (int i = 0; i < n && k > 0; i++) {
        if (!used[order[i]]) {
          used[order[i]] = 1;
          k--;
          last = order[i];
        }
      }
      cout << last << '\n';
    } else {
      used[k] = 0;
      cnt = 0;
      remove(root);
      cout << cnt << '\n';
    }
  }
  return 0;
}

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