oj.uz

Submission #102187

# Submission time Handle Problem Language Result Execution time Memory
102187 2019-03-23T10:24:18 Z WLZ Ball Machine (BOI13_ballmachine) C++17
100 / 100
 504 ms 35320 KB 
#include <bits/stdc++.h>
using namespace std;
 
vector<int> p, order, depth, pos, used, mn;
vector< vector<int> > children, up;
int root, cnt, max_log;
 
void dfs(int u, int par, int d) {
  mn[u] = 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]) {
    dfs(v, u, d + 1);
    mn[u] = min(mn[u], mn[v]);
  }
}

void preorder(int u) {
  priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
  for (auto& v : children[u]) {
    pq.push({mn[v], v});
  }
  while (!pq.empty()) {
    preorder(pq.top().second);
    pq.pop();
  }
  order.push_back(u);
}

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);
  mn.resize(n + 1);
  dfs(root, root, 0);
  preorder(root);
  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) {
          cout << last << '\n';
          break;
        }
      }
    } 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;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 246 ms 14452 KB Output is correct
3 Correct 147 ms 14848 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 11 ms 1152 KB Output is correct
10 Correct 38 ms 3840 KB Output is correct
11 Correct 292 ms 14376 KB Output is correct
12 Correct 137 ms 14580 KB Output is correct
13 Correct 200 ms 14404 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 6804 KB Output is correct
2 Correct 494 ms 28456 KB Output is correct
3 Correct 188 ms 21456 KB Output is correct
4 Correct 169 ms 8792 KB Output is correct
5 Correct 129 ms 8548 KB Output is correct
6 Correct 102 ms 8716 KB Output is correct
7 Correct 122 ms 7288 KB Output is correct
8 Correct 47 ms 6904 KB Output is correct
9 Correct 322 ms 28708 KB Output is correct
10 Correct 411 ms 28360 KB Output is correct
11 Correct 337 ms 28324 KB Output is correct
12 Correct 410 ms 24868 KB Output is correct
13 Correct 281 ms 31140 KB Output is correct
14 Correct 171 ms 21520 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 14312 KB Output is correct
2 Correct 408 ms 25544 KB Output is correct
3 Correct 326 ms 28148 KB Output is correct
4 Correct 265 ms 22900 KB Output is correct
5 Correct 287 ms 22844 KB Output is correct
6 Correct 284 ms 22688 KB Output is correct
7 Correct 320 ms 20432 KB Output is correct
8 Correct 257 ms 28152 KB Output is correct
9 Correct 421 ms 29044 KB Output is correct
10 Correct 497 ms 28528 KB Output is correct
11 Correct 437 ms 28488 KB Output is correct
12 Correct 465 ms 25820 KB Output is correct
13 Correct 504 ms 35320 KB Output is correct
14 Correct 354 ms 21552 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 29144 KB Output is correct
2 Correct 443 ms 25668 KB Output is correct
3 Correct 337 ms 35148 KB Output is correct
4 Correct 424 ms 29184 KB Output is correct
5 Correct 395 ms 28572 KB Output is correct
6 Correct 348 ms 28452 KB Output is correct
7 Correct 435 ms 25684 KB Output is correct
8 Correct 300 ms 34936 KB Output is correct
9 Correct 195 ms 21480 KB Output is correct