Submission #588676

#	Time	Username	Problem	Language	Result	Execution time	Memory
588676		MilosMilutinovic	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	258 ms	31876 KiB

ballmachine

/**
 *    author:  wxhtzdy
 *    created: 03.07.2022 19:51:50
**/
#include <bits/stdc++.h>

using namespace std;

template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, q;
  cin >> n >> q;
  vector<vector<int>> g(n);
  int root;
  for (int i = 0; i < n; i++) {
    int p;
    cin >> p;
    --p;
    if (p == -1) {
      root = i;
    } else {
      g[p].push_back(i);
    }
  }
  const int L = 20;
  vector<vector<int>> jump(n, vector<int>(L));
  vector<int> tin(n);
  vector<int> tout(n);
  vector<int> dep(n);
  vector<int> mn(n);
  int T = 0;
  function<void(int, int)> Dfs = [&](int v, int pr) {
    tin[v] = ++T;
    dep[v] = dep[pr] + 1;
    jump[v][0] = pr;
    mn[v] = v;
    for (int u : g[v]) {
      Dfs(u, v);
      mn[v] = min(mn[v], mn[u]);
    }
    tout[v] = ++T;
  };
  Dfs(root, root);
  for (int i = 0; i < n; i++) {
    sort(g[i].begin(), g[i].end(), [&](int x, int y) {
      return mn[x] < mn[y];
    });
  }
  vector<int> order(n);
  T = 0;
  Dfs = [&](int v, int pr) {
    order[v] = ++T;
    for (int u : g[v]) {
      if (u != pr) {
        Dfs(u, v);
      }
    }  
  };
  Dfs(root, root);                                           
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      jump[i][j] = jump[jump[i][j - 1]][j - 1];
    }
  }
  vector<int> deg(n);
  set<pair<int, int>> st;
  for (int i = 0; i < n; i++) {
    if (g[i].empty()) {
      st.emplace(order[i], i);
    }
  }
  fenwick<int> fenw(2 * (n + 1));      
  function<void(int, int)> Add = [&](int x, int v) {
    fenw.modify(tin[x], v);
    fenw.modify(tout[x], -v);
  };       
  function<void(int)> Ins = [&](int x) {
    deg[x] += 1;
    if (deg[x] == (int) g[x].size()) {
      st.emplace(order[x], x);
    }
  };
  function<void(int)> Del = [&](int x) {
    if (deg[x] == (int) g[x].size()) {
      st.erase(st.find(make_pair(order[x], x)));
    }
    deg[x] -= 1;
  };
  while (q--) {
    int op, x;
    cin >> op >> x;
    if (op == 1) {
      int ans;
      while (x--) {
        auto it = st.begin();
        int i = it->second;
        st.erase(it);
        Add(i, +1);
        if (i != root) {
          Ins(jump[i][0]);
        }
        ans = i;      
      }
      cout << ans + 1 << '\n';
    } else {
      --x;
      int cnt = fenw.get(tout[x]);
      cout << cnt << '\n';
      for (int i = L - 1; i >= 0; i--) {
        if (cnt >> i & 1) {
          x = jump[x][i];
        }
      }
      Add(x, -1);
      if (x != root) {
        Del(jump[x][0]);
      }  
      st.emplace(order[x], x);
    }
  }
  return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:129:26: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  129 |       cout << ans + 1 << '\n';
      |                          ^~~~
ballmachine.cpp:124:9: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |         if (i != root) {
      |         ^~

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