제출 #1235081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235081		avighna	Prize (CEOI22_prize)	C++20	0 / 100	910 ms	1114112 KiB

Main

#include <bits/stdc++.h>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  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 = 0, 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);
  auto dfs = [&](auto &&self, int u, int p) -> void {
    if (subset.size() < k) {
      subset.push_back(u);
    }
    for (auto &i : adj[u]) {
      depth[i] = depth[u] + 1, lift[i][0] = u;
      self(self, i, u);
    }
  };
  dfs(dfs, 1, 0);
  lift[1][0] = 1;

  for (auto &i : subset) {
    std::cout << i << ' ';
  }
  std::cout << std::flush;
  std::vector wt_lift(n + 1, std::array<int64_t, 20>());
  for (int i = 1; i < k; ++i) {
    std::cout << "? 1 " << subset[i] << std::endl;
    std::cin >> wt_lift[subset[i]][0];
    wt_lift[subset[i]][0] -= wt_lift[lift[subset[i]][0]][0];
  }
  for (int bt = 1; bt < 20; ++bt) {
    for (int i = 1; i <= n; ++i) {
      lift[i][bt] = lift[lift[i][bt - 1]][bt - 1];
      wt_lift[i][bt] = wt_lift[i][bt - 1] + wt_lift[lift[i][bt - 1]][bt - 1];
    }
  }

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

  std::vector<std::pair<int, int>> questions(t);
  for (auto &[a, b] : questions) {
    std::cin >> a >> b;
  }
  for (auto &[a, b] : questions) {
    std::cout << "! " << dist(a, b) << '\n';
  }
  std::cout << std::flush;
}

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