Submission #1235094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235094		avighna	Prize (CEOI22_prize)	C++20	0 / 100	1136 ms	174308 KiB

Main

#include <bits/stdc++.h>

int main() {
  int n, k, q, t;
  std::cin >> n >> k >> q >> t;
  std::vector<std::vector<int>> adj(n + 1);
  for (int i = 0, x; i < n; ++i) {
    std::cin >> x;
  }
  for (int i = 1, x; i <= n; ++i) {
    std::cin >> x;
    if (x != -1) {
      adj[i].push_back(x);
      adj[x].push_back(i);
    }
  }
  std::vector<int> subset;
  std::vector lift(n + 1, std::array<int, 20>());
  std::vector<int> depth(n + 1);
  std::vector<int64_t> real_dep(n + 1);
  auto dfs = [&](auto &&self, int u, int p) -> void {
    if (subset.size() < k) {
      subset.push_back(u);
    }
    for (auto &i : adj[u]) {
      if (i == p) {
        continue;
      }
      depth[i] = depth[u] + 1, lift[i][0] = u;
      self(self, i, u);
    }
  };
  dfs(dfs, 1, 0);
  lift[1][0] = 1;
  for (int bt = 1; bt < 20; ++bt) {
    for (int i = 1; i <= n; ++i) {
      lift[i][bt] = lift[lift[i][bt - 1]][bt - 1];
    }
  }

  for (auto &i : subset) {
    std::cout << i << ' ';
  }
  std::cout << std::endl;
  for (int i = 1; i < k; ++i) {
    std::cout << "? 1 " << subset[i] << std::endl;
    std::cin >> real_dep[subset[i]] >> real_dep[subset[i]] >> real_dep[subset[i]] >> real_dep[subset[i]];
  }
  std::cout << "!" << std::endl;

  auto lca = [&](int u, int v) {
    if (depth[u] < depth[v]) {
      std::swap(u, v);
    }
    int k = depth[u] - depth[v];
    for (int bt = 0; bt < 20; ++bt) {
      if (k & (1 << bt)) {
        u = lift[u][bt];
      }
    }
    if (u == v) {
      return u;
    }
    for (int bt = 19; bt >= 0; --bt) {
      if (lift[u][bt] != lift[v][bt]) {
        u = lift[u][bt], v = lift[v][bt];
      }
    }
    return lift[u][0];
  };

  std::vector<std::pair<int, int>> questions(t);
  for (auto &[a, b] : questions) {
    std::cin >> a >> b;
  }
  for (auto &[a, b] : questions) {
    int64_t d = real_dep[a] + real_dep[b] - 2 * real_dep[lca(a, b)];
    std::cout << d << ' ' << d << std::endl;
  }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24