oj.uz

Submission #679617

# Submission time Handle Problem Language Result Execution time Memory
679617 2023-01-08T16:56:49 Z peijar Ball Machine (BOI13_ballmachine) C++17
100 / 100
 316 ms 31428 KB 
#include <bits/stdc++.h>
#include <sys/ucontext.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 1e5;
const int MAXP = 20;

vector<int> adj[MAXN];
int par[MAXP][MAXN];
int Time;
int order[MAXN];
int depth[MAXN];
int smallestSub[MAXN];

void init(int u, int p) {
  smallestSub[u] = u;
  for (int v : adj[u])
    if (v != p) {
      init(v, u);
      smallestSub[u] = min(smallestSub[u], smallestSub[v]);
    }
}

void dfs(int u, int p) {
  par[0][u] = p;
  for (int i = 0; i < MAXP - 1; ++i)
    par[i + 1][u] = par[i][par[i][u]];
  sort(adj[u].begin(), adj[u].end(),
       [&](int s, int t) { return smallestSub[s] < smallestSub[t]; });
  for (int v : adj[u]) {
    depth[v] = 1 + depth[u];
    dfs(v, u);
  }
  order[u] = Time++;
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommet, nbRequetes;
  cin >> nbSommet >> nbRequetes;

  int root = -1;
  for (int i = 0; i < nbSommet; ++i) {
    int p;
    cin >> p;
    --p;
    if (p != -1)
      adj[p].push_back(i);
    else
      root = i;
  }

  init(root, root);
  dfs(root, root);

  auto compare = [&](int u, int v) { return order[u] > order[v]; };

  vector<bool> isFilled(nbSommet);
  priority_queue<int, vector<int>, decltype(compare)> pq(compare);

  for (int u = 0; u < nbSommet; ++u)
    pq.push(u);
  for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
    int t, x;
    cin >> t >> x;
    if (t == 1) {
      int u = -1;
      for (int i = 0; i < x; ++i) {
        u = pq.top();
        pq.pop();
        isFilled[u] = true;
      }
      cout << u + 1 << '\n';
    } else {
      --x;
      assert(isFilled[x]);
      int u = x;
      for (int p = MAXP - 1; p >= 0; --p)
        if (isFilled[par[p][x]])
          x = par[p][x];
      isFilled[x] = false;
      pq.emplace(x);
      cout << depth[u] - depth[x] << '\n';
    }
  }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 211 ms 16376 KB Output is correct
3 Correct 64 ms 16620 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 7 ms 3672 KB Output is correct
10 Correct 22 ms 6280 KB Output is correct
11 Correct 216 ms 16488 KB Output is correct
12 Correct 62 ms 16588 KB Output is correct
13 Correct 152 ms 16424 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8316 KB Output is correct
2 Correct 307 ms 27088 KB Output is correct
3 Correct 71 ms 23328 KB Output is correct
4 Correct 78 ms 10320 KB Output is correct
5 Correct 80 ms 10224 KB Output is correct
6 Correct 81 ms 10228 KB Output is correct
7 Correct 77 ms 9192 KB Output is correct
8 Correct 29 ms 8272 KB Output is correct
9 Correct 276 ms 27444 KB Output is correct
10 Correct 316 ms 27040 KB Output is correct
11 Correct 180 ms 27012 KB Output is correct
12 Correct 294 ms 25040 KB Output is correct
13 Correct 98 ms 28132 KB Output is correct
14 Correct 67 ms 23364 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 15260 KB Output is correct
2 Correct 281 ms 25528 KB Output is correct
3 Correct 165 ms 25880 KB Output is correct
4 Correct 172 ms 22804 KB Output is correct
5 Correct 170 ms 22468 KB Output is correct
6 Correct 179 ms 22452 KB Output is correct
7 Correct 183 ms 21144 KB Output is correct
8 Correct 161 ms 25820 KB Output is correct
9 Correct 274 ms 27588 KB Output is correct
10 Correct 312 ms 27176 KB Output is correct
11 Correct 305 ms 27104 KB Output is correct
12 Correct 289 ms 25704 KB Output is correct
13 Correct 269 ms 31428 KB Output is correct
14 Correct 250 ms 23420 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 27608 KB Output is correct
2 Correct 308 ms 25640 KB Output is correct
3 Correct 116 ms 31296 KB Output is correct
4 Correct 259 ms 27688 KB Output is correct
5 Correct 295 ms 27144 KB Output is correct
6 Correct 187 ms 27132 KB Output is correct
7 Correct 279 ms 25580 KB Output is correct
8 Correct 108 ms 31292 KB Output is correct
9 Correct 72 ms 23436 KB Output is correct