Submission #303731

#	Time	Username	Problem	Language	Result	Execution time	Memory
303731		quocnguyen1012	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	288 ms	30840 KiB

ballmachine

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

int N, Q, mn[maxn], pos[maxn], cnt, col[maxn], par[maxn][20];
vector<int> adj[maxn];

void dfs(int u) {
  for (int i = 1; i <= 19; ++i) {
    par[u][i] = par[par[u][i - 1]][i - 1];
  }
  mn[u] = u;
  for (int v : adj[u]) {
    par[v][0] = u;
    dfs(v);
    mn[u] = min(mn[u], mn[v]);
  }
}

void go(int u) {
  vector<ii> order;
  for (int v : adj[u]) {
    order.eb(mn[v], v);
  }
  sort(order.begin(), order.end());
  for (auto & v : order) {
    go(v.se);
  }
  pos[u] = ++cnt;
}

signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> Q;
  int root;
  for (int i = 1; i <= N; ++i) {
    int p; cin >> p;
    if (!p) root = i;
    else adj[p].eb(i);
  }
  dfs(root);
  go(root);
  set<ii> emp;
  for (int i = 1; i <= N; ++i) {
    emp.insert({pos[i], i});
  }
  while (Q--) {
    int type, x; cin >> type >> x;
    if (type == 1) {
      int res = 0;
      while (x--) {
        auto it = emp.begin();
        res = (*it).se;
        col[res] = 1;
        emp.erase(it);
      }
      cout << res << '\n';
    } else {
      int res = 0;
      for (int i = 18; i >= 0; --i) {
        if (col[par[x][i]]) {
          res += (1 << i);
          x = par[x][i];
        }
      }
      emp.insert(mp(pos[x], x));
      col[x] = 0;
      cout << res << '\n';
    }
  }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:57:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |   go(root);
      |   ~~^~~~~~

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