oj.uz

Submission #791147

# Submission time Handle Problem Language Result Execution time Memory
791147 2023-07-23T13:04:36 Z tch1cherin Ball Machine (BOI13_ballmachine) C++17
100 / 100
 234 ms 29248 KB 
#include <bits/stdc++.h>
using namespace std;

// Can also be done with std::set<std::tuple<int, int, int>>
// But segment tree seems cleaner and easier to debug (no off-by-one errors)
struct segment_tree {
  int size;
  vector<int> tree;

  segment_tree(int n) : size(2 << __lg(n)), tree(4 << __lg(n), INT_MIN) {
    iota(tree.begin() + size, tree.end(), 0);
  }

  void propagate(int x) {
    if (tree[x] != INT_MIN) {
      tree[x * 2] = tree[x * 2 + 1] = tree[x];
      tree[x] = INT_MIN;  
    }
  }

  void modify(int l, int r, int v) {
    modify(l, r + 1, v, 1, 0, size);
  }

  void modify(int l, int r, int v, int x, int lx, int rx) {
    if (lx >= r || rx <= l) {
      return;
    } else if (lx >= l && rx <= r) {
      tree[x] = v;
    } else {
      propagate(x);
      int mid = (lx + rx) / 2;
      modify(l, r, v, x * 2, lx, mid);
      modify(l, r, v, x * 2 + 1, mid, rx);
    }
  }

  int get(int i) {
    return get(i, 1, 0, size);
  }

  int get(int i, int x, int lx, int rx) {
    if (tree[x] != INT_MIN) {
      return tree[x]; 
    } else {
      int mid = (lx + rx) / 2;
      if (i < mid) {
        return get(i, x * 2, lx, mid);
      } else {
        return get(i, x * 2 + 1, mid, rx);
      }
    }
  }
};

const int MAX_N = 1e5 + 5, L = __lg(MAX_N) + 1;
vector<int> G[MAX_N];
int dp[MAX_N][L], depth[MAX_N] = {}, min_value[MAX_N], tin[MAX_N], tout[MAX_N], parent[MAX_N], pos[MAX_N];
vector<int> ord;
int T = 0, root;

void DFS(int u) {
  dp[u][0] = parent[u] == -1 ? u : parent[u];
  for (int i = 1; i < L; i++) {
    dp[u][i] = dp[dp[u][i - 1]][i - 1];
  }
  tin[u] = T++;
  tout[u] = tin[u];
  for (int v : G[u]) {
    depth[v] = depth[u] + 1;
    DFS(v);
    min_value[u] = min(min_value[u], min_value[v]); 
    tout[u] = max(tout[u], tout[v]);
  }
  sort(G[u].begin(), G[u].end(), [](int i, int j) {
    return min_value[i] < min_value[j];
  });
}

void find_order(int u) {
  for (int v : G[u]) {
    find_order(v);
  }
  ord.push_back(u);
  pos[u] = (int)ord.size() - 1;
}

int find_last(int u, int v) {
  if (v == -1) {
    return root;
  }
  for (int i = L - 1; i >= 0; i--) {
    int x = dp[u][i];
    if (!(tin[x] <= tin[v] && tout[v] <= tout[x])) {
      u = x;  
    }
  }
  return u;
}

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++) {
    cin >> parent[i];
    parent[i]--;
    if (parent[i] == -1) {
      root = i;
    } else {
      G[parent[i]].push_back(i);
    }
  }
  DFS(root);
  ord.reserve(N);
  find_order(root);
  set<int> not_used;
  for (int i = 0; i < N; i++) {
    not_used.insert(i);
  }
  segment_tree tree(N);
  while (Q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int k;
      cin >> k;
      for (int i = 0; i < k; i++) {
        int u = ord[*not_used.begin()];
        not_used.erase(not_used.begin());
        if (i == k - 1) {
          cout << 1 + u << "\n";
        }
        tree.modify(tin[u], tout[u], parent[u]);
      }
    } else {
      int x;
      cin >> x;
      x--;
      int new_up = find_last(x, tree.get(tin[x]));
      cout << depth[x] - depth[new_up] << "\n";
      tree.modify(tin[new_up], tout[new_up], new_up);
      not_used.insert(pos[new_up]);
    }
  }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 124 ms 13584 KB Output is correct
3 Correct 57 ms 13796 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2884 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 8 ms 3388 KB Output is correct
10 Correct 24 ms 5428 KB Output is correct
11 Correct 118 ms 13900 KB Output is correct
12 Correct 57 ms 13836 KB Output is correct
13 Correct 110 ms 13644 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7788 KB Output is correct
2 Correct 234 ms 23788 KB Output is correct
3 Correct 71 ms 19296 KB Output is correct
4 Correct 81 ms 9368 KB Output is correct
5 Correct 82 ms 9164 KB Output is correct
6 Correct 78 ms 8960 KB Output is correct
7 Correct 93 ms 8400 KB Output is correct
8 Correct 38 ms 7728 KB Output is correct
9 Correct 144 ms 24196 KB Output is correct
10 Correct 165 ms 23800 KB Output is correct
11 Correct 160 ms 23792 KB Output is correct
12 Correct 156 ms 21404 KB Output is correct
13 Correct 86 ms 26108 KB Output is correct
14 Correct 72 ms 19280 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 13528 KB Output is correct
2 Correct 189 ms 22024 KB Output is correct
3 Correct 111 ms 24008 KB Output is correct
4 Correct 105 ms 20232 KB Output is correct
5 Correct 113 ms 19804 KB Output is correct
6 Correct 108 ms 19816 KB Output is correct
7 Correct 139 ms 18252 KB Output is correct
8 Correct 110 ms 23988 KB Output is correct
9 Correct 163 ms 24316 KB Output is correct
10 Correct 178 ms 24044 KB Output is correct
11 Correct 172 ms 23968 KB Output is correct
12 Correct 172 ms 21952 KB Output is correct
13 Correct 182 ms 29248 KB Output is correct
14 Correct 173 ms 19328 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 24492 KB Output is correct
2 Correct 165 ms 21960 KB Output is correct
3 Correct 114 ms 29160 KB Output is correct
4 Correct 172 ms 24476 KB Output is correct
5 Correct 194 ms 23968 KB Output is correct
6 Correct 159 ms 23916 KB Output is correct
7 Correct 173 ms 21968 KB Output is correct
8 Correct 97 ms 29136 KB Output is correct
9 Correct 80 ms 19284 KB Output is correct