Submission #791147

#	Time	Username	Problem	Language	Result	Execution time	Memory
791147		tch1cherin	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	234 ms	29248 KiB

ballmachine

#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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5