Submission #102184

#	Time	Username	Problem	Language	Result	Execution time	Memory
102184		WLZ	Ball Machine (BOI13_ballmachine)	C++17	45.56 / 100	1082 ms	33536 KiB

ballmachine

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

vector<int> p, order, depth, pos;
vector< vector<int> > children, up;
vector<int> used;
int root, cnt, max_log;

pair<int, vector<int> > dfs(int u, int par, int d) {
  int mn = 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]) {
    tmp.push_back(dfs(v, u, d + 1));
    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};
}

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);
  order = dfs(root, root, 0).second;
  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) {
          break;
        }
      }
      cout << last << '\n';
    } 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;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:75:23: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
       cout << last << '\n';
                       ^~~~

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