P11988 [JOIST 2025] 宇宙怪盗 题解

Description

这是一道交互题。本题中，交互库可能是自适应的。

有一张 $N$ 个点 $M$ 条边的无向连通图。点编号 $0\sim N-1$，边编号 $0\sim M-1$，第 $i$（$0 \leq i \leq M-1$）条边双向连接点 $U_i$ 和 $V_i$。

有一把钥匙藏在某一个点上，而有一个宝箱藏在另一个节点上。你需要通过至多 $300$ 次询问确定钥匙所在的节点编号和宝箱所在的节点编号：

询问

对于 $i=0,1,\ldots,M-1$，将第 $i$ 条边设置为单向通行。

• 具体地，构造长度为 $M$ 的 $01$ 序列 $x_0\sim x_{M-1}$。$x_i=0$ 表示第 $i$ 条边从 $U_i$ 指向 $V_i$，$x_i=1$ 表示第 $i$ 条边从 $V_i$ 指向 $U_i$。

交互库会返回，在这张图中，是否能从钥匙所在的节点到达宝箱所在的节点。

你需要用至多 $70$ 次询问确定钥匙所在的节点 $A$ 和宝箱所在的节点 $B$。

$N\leq 10000,M\leq 15000$。

Solution

先考虑树怎么做。注意到我们如果能够找到任何一个合法的定向方案使得 $A$ 能到 $B$，那么把这棵树的拓扑序拿出来就能二分了。因为 $A$ 此时拓扑序一定在 $B$ 之前，二分找到最长的前缀 $[1,d]$，让拓扑序数组上 $[1,d]$ 和 $[d+1,n]$ 之间的边反向，如果 $A$ 还能到 $B$ 就说明 $A$ 在 $[d+1,n]$ 里，否则 $A$ 在 $[1,d]$ 里。对 $B$ 是同理的。

现在再来考虑怎么找到一组这样的定向方案。

对于菊花的情况，由于 $A$ 和 $B$ 至少有一个二进制位不同，所以选择一个二进制位，让这一位为 $0$ 的边方向指向根，为 $1$ 的方向指向叶子。再询问将这个图反向的结果，通过 $2\log N$ 次询问一定能够得到满足条件的方案。

对于普通树，考虑通过点分治将问题变得类似菊花，即钦定 $A$ 和 $B$ 的路径经过当前的根 $x$，我们让 $x$ 每个儿子子树内的边方向相同，就变成菊花了，然后让点分树同层的 $x$ 并行做，总次数是 $O(\log^2N)$。

注意到 $x$ 是重心，所以 $x$ 儿子子树最大的大小不超过 $\frac{sz_x}{2}$，容易发现一定存在 $x$ 儿子的一个划分方案使得每个集合内的子树大小和在 $\left[\frac{sz_x}{3},\frac{2sz_x}{3}\right]$ 内，随便找到一个这样的划分，将这两个划分看成两个子树做上面的做法，再对这两个划分分治即可。

总次数为 $2\log_{\frac{3}{2}}N+2\log_2N$。

Code

#include "thief.h"
#include <bits/stdc++.h>

#ifdef ORZXKR
#include "grader.cpp"
#endif

const int kMaxN = 6e4 + 5, kMaxM = 2e4 + 5;

int n, m, rt, mxd, cnt;
int u[kMaxM], v[kMaxM], sz[kMaxN], mx[kMaxN], dep[kMaxN], real[kMaxN], now[kMaxN];
bool ont[kMaxM], del[kMaxN];
std::vector<std::pair<int, int>> G[kMaxN], T[kMaxN];
std::vector<int> eid[kMaxN];

void add(int u, int v, int id) {
  T[u].emplace_back(v, id), T[v].emplace_back(u, id);
}

bool ask(std::vector<int> perm) {
  static int pos[kMaxN];
  std::vector<int> vec(m);
  for (int i = 1; i <= n; ++i) pos[perm[i - 1]] = i;
  for (int i = 1; i <= m; ++i) vec[i - 1] = (pos[u[i]] > pos[v[i]]);
  return query(vec);
}

bool ask(bool *dir, bool op = 0) {
  std::vector<int> vec(m);
  for (int i = 1; i <= m; ++i) vec[i - 1] = dir[i] ^ op;
  return query(vec);
}

struct Node {
  int deg[kMaxN] = {0}, _deg[kMaxN] = {0};
  std::vector<int> G[kMaxN];
  void add(int u, int v) { G[u].emplace_back(v), ++_deg[v]; }
  std::vector<int> getperm() {
    std::queue<int> q;
    std::vector<int> perm;
    for (int i = 1; i <= n; ++i) {
      deg[i] = _deg[i];
      if (!deg[i])
        q.emplace(i);
    }
    for (; !q.empty();) {
      int u = q.front(); q.pop();
      perm.emplace_back(u);
      for (auto v : G[u]) {
        if (!--deg[v]) q.emplace(v);
      }
    }
    return perm;
  }
  bool query() { return ask(getperm()); }
} gr[100];

void build() {
  static bool vis[kMaxN];
  std::fill_n(vis + 1, n, 0);
  std::function<void(int)> dfs = [&] (int u) {
    vis[u] = 1;
    for (auto [v, id] : G[u]) {
      if (!vis[v]) {
        ont[id] = 1, T[u].emplace_back(v, id), T[v].emplace_back(u, id);
        dfs(v);
      }
    }
  };
  dfs(1);
}

void getsz(int u, int fa) {
  sz[u] = 1, mx[u] = 0;
  for (auto [v, id] : T[u]) {
    if (v == fa || del[v]) continue;
    getsz(v, u);
    sz[u] += sz[v], mx[u] = std::max(mx[u], sz[v]);
  }
}

void getrt(int u, int fa, int tot) {
  mx[u] = std::max(mx[u], tot - sz[u]);
  if (mx[u] < mx[rt]) rt = u;
  for (auto [v, id] : T[u]) {
    if (v == fa || del[v]) continue;
    getrt(v, u, tot);
  }
}

void dfs(int u, int fa, int rt) {
  dep[u] = dep[fa] + 1;
  now[real[u]] = u;
  for (auto [v, id] : T[u]) {
    if (v == fa || del[v]) continue;
    if (id) eid[rt].emplace_back(id);
    dfs(v, u, rt);
  }
}

void solve(int u, int d) {
  static int pid[kMaxN];
  mx[rt = 0] = 1e9, getsz(u, 0), getrt(u, 0, sz[u]);
  u = rt, dep[u] = 1, now[real[u]] = u;
  std::vector<int> vid;
  int tot = 0;
  for (auto [v, id] : T[u]) {
    if (del[v]) continue;
    eid[v] = (id ? std::vector<int>{id} : std::vector<int>{});
    pid[v] = id;
    vid.emplace_back(v), dfs(v, u, v);
    tot += eid[v].size();
  }
  std::sort(vid.begin(), vid.end(), [&] (int i, int j) { return eid[i].size() < eid[j].size(); });
  if (!tot) return;
  int id1 = 0, id2 = 0;
  std::vector<int> e1, e2;
  for (int i = 0, now = 0; i < vid.size(); ++i) {
    now += eid[vid[i]].size();
    if (now >= tot / 3) {
      real[id1 = ++cnt] = real[u];
      if (i + 1 < vid.size()) real[id2 = ++cnt] = real[u];
      for (int j = 0; j <= i; ++j) {
        int v = vid[j];
        for (auto id : eid[v]) e1.emplace_back(id);
        add(id1, vid[j], pid[vid[j]]);
      }
      for (int j = i + 1; j < vid.size(); ++j) {
        int v = vid[j];
        for (auto id : eid[v]) e2.emplace_back(id);
        add(id2, vid[j], pid[vid[j]]);
      }
      // std::cerr << "fuckkk " << u << ' ' << tot << ' ' << now << ' ' << tot - now << '\n';
      break;
    }
  }
  for (auto id : e1) {
    int x = ::u[id], y = ::v[id];
    if (dep[now[x]] > dep[now[y]]) std::swap(x, y);
    gr[2 * d - 1].add(x, y), gr[2 * d].add(y, x);
  }
  for (auto id : e2) {
    int x = ::u[id], y = ::v[id];
    if (dep[now[x]] > dep[now[y]]) std::swap(x, y);
    gr[2 * d - 1].add(y, x), gr[2 * d].add(x, y);
  }
  mxd = std::max(mxd, 2 * d);
  del[u] = 1;
  if (tot == 1) return;
  assert(id1 && id2);
  // std::cerr << "shabi " << u << ' ' << cnt << ' ' << d << ' ' << sz[u] << ' ' << id1 << ' ' << id2 << '\n';
  // std::cerr << e1.size() << ' ' << e2.size() << '\n';
  if (id1) solve(id1, d + 1);
  if (id2) solve(id2, d + 1);
}

void solve(int N, int M, std::vector<int> U, std::vector<int> V) {
  n = N, m = M;
  for (int i = 1; i <= m; ++i) {
    u[i] = U[i - 1] + 1, v[i] = V[i - 1] + 1;
    G[u[i]].emplace_back(v[i], i);
    G[v[i]].emplace_back(u[i], i);
  }
  build();
  cnt = n;
  for (int i = 1; i <= n; ++i) real[i] = i;
  solve(1, 1);
  for (int d = 1; d <= mxd; ++d) {
    // std::cerr << gr[d].query() << '\n';
    if (gr[d].query()) {
      auto perm = gr[d].getperm();
      static int pos[kMaxN];
      for (int i = 1; i <= n; ++i) pos[perm[i - 1]] = i;
      int a = 0, b = 0;
      {
        int L = 1, R = n + 1, res = 1;
        while (L + 1 < R) {
          int mid = (L + R) >> 1;
          std::vector<int> vec(m);
          for (int i = 1; i <= m; ++i) {
            int x = pos[u[i]], y = pos[v[i]];
            if (x < mid || y < mid) vec[i - 1] = (x < y);
            else vec[i - 1] = (x > y);
          }
          if (query(vec)) L = res = mid;
          else R = mid;
        }
        a = perm[res - 1];
      }
      {
        int L = 0, R = n, res = n;
        while (L + 1 < R) {
          int mid = (L + R) >> 1;
          std::vector<int> vec(m);
          for (int i = 1; i <= m; ++i) {
            int x = pos[u[i]], y = pos[v[i]];
            if (x > mid || y > mid) vec[i - 1] = (x < y);
            else vec[i - 1] = (x > y);
          }
          if (query(vec)) R = res = mid;
          else L = mid;
        }
        b = perm[res - 1];
      }
      answer(a - 1, b - 1);
      return;
    }
    // std::cerr << gr[i].ask() << '\n';
  }
}