Submission #790879

#	Time	Username	Problem	Language	Result	Execution time	Memory
790879		tch1cherin	Ball Machine (BOI13_ballmachine)	C++17	13.47 / 100	1093 ms	82492 KiB

ballmachine

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

const int MAX_N = 1e5 + 5;
vector<int> G[MAX_N];
priority_queue<pair<int, int>> go[MAX_N];  
int min_value[MAX_N], cnt_empty[MAX_N], parent[MAX_N], balls[MAX_N] = {}, root;
queue<int> q;

void DFS(int u) {
  cnt_empty[u] = 1;
  for (int v : G[u]) {
    DFS(v);
    cnt_empty[u] += cnt_empty[v];
    go[u].push({-min_value[v], v});
    min_value[u] = min(min_value[u], min_value[v]);
  }
  sort(G[u].begin(), G[u].end(), [](int i, int j) {
    return min_value[i] < min_value[j];
  });
}

void rolldown(int u, bool insert = true) {
  if (go[u].empty()) {
    return;
  }
  int v = go[u].top().second;
  go[u].pop();
  balls[u]--, balls[v]++;
  cnt_empty[v]--;
  if (insert) {
    q.push(v);
  }
  if (cnt_empty[v] > 0) {
    go[u].push({-min_value[v], v});
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, Q;
  cin >> N >> Q;
  iota(min_value, min_value + N, 0);
  for (int i = 0; i < N; i++) {
    int p;
    cin >> p;
    p--;
    parent[i] = p;
    if (p == -1) {
      root = i;
    } else {
      G[p].push_back(i);
    }
  }
  DFS(root);
  while (Q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int k;
      cin >> k;
      for (int i = 0; i < k - 1; i++) {
        q.push(root);
        balls[root]++;
        cnt_empty[root]--;
      }
      while (!q.empty()) {
        rolldown(q.front());
        q.pop();
      }
      q.push(root);
      balls[root]++, cnt_empty[root]--;
      int ans;
      while (!q.empty()) {
        rolldown(ans = q.front());
        q.pop();
      }
      cout << 1 + ans << "\n";
    } else {
      int x;
      cin >> x;
      x--;
      balls[x]--;
      int ans = 0;
      while (x != -1) {
        cnt_empty[x]++;
        go[parent[x]].push({-min_value[x], x});
        if (balls[x] > 0) {
          rolldown(x, false);
          ans++;
        }
        x = parent[x];
      }
      cout << ans << "\n";
    }
  }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:78:26: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |       cout << 1 + ans << "\n";
      |                          ^~~~

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