IOI2024 D2T3 sol

· · 题解

感谢 @dead_X 在思考过程中提供的一些帮助。

我们不妨从 Subtask 3 入手。我们首先分析每次询问的性质，考虑到连通块这一结构，能够得到接下来的用途：

Usage 1：选择原图的一个点独立集 S，在询问中保持它们的颜色不变，而其他点统一染为某个颜色 c。我们在钦定独立集中没有一个点的颜色是 c 的前提下算出连通块个数，那么如果询问后连通块个数不匹配，就说明集合 S 中至少有一个点的颜色是 c。

假设我们选择了 x 个点，根据独立集的性质，这 x 个点各自形成一个同色连通块。对于其他的点，我们求出这些点在原图上构成的连通块数 y。那么此时，连通块个数匹配当且仅当询问的返回值为 x + y。

这一个用途可以很自然的带入到链情形中。具体的，考虑链上最容易找到的两个独立集：下标为奇数的点形成的集合，以及下标为偶数的点形成的集合。我们将集合写作序列，尝试通过二分找到第一个颜色等于 c 的点，这个操作即可通过 Usage 1 做到。随后，将这个点丢弃，并继续二分接下来一个颜色为 c 的点。在每次二分之前，需要提前跑一次对全序列的 Usage 1，保证本次二分是有效的。

接下来分析这个方案用到的询问数。对每个独立集的序列，需要进行若干次二分试探，其中 n 次是失败的，而对于每个点，都对应了一次成功的试探，以及后面的二分流程。那么，假设当前的颜色种类为 N，而点的个数为 C，则所需的询问数存在一个上界 2N + \sum_{i=1}^{C} (\lceil \log i \rceil + 1)。这里需要注意的是，每次二分成功后，序列的长度都会减少 1，对应的二分次数也可能会减少。

这个思想可以很自然的套用到任何一个二分图上，对应的询问数也是类似的。

接下来考虑如何实现任意图的问题。我们不能对任意的图进行黑白染色，所以我们需要尝试找到黑白染色的方案，并在这个方案下套用二分图的做法。我们接下来介绍一个比较重要的性质。

下面，为了区分黑白染色和题目给出的每个点颜色，我们称黑白染色的结果为“黑类”和“白类”，而维持原题目对颜色的描述。

性质：假如我们已经知道某条边 (x, y) 连接的两个点 x 和 y 颜色不同，那么我们可以将这两个点同时归为黑类或者白类，而对于一个分类方案，唯一的需求是每个点都需要和一个不同类的点相邻。我们将会证明，必然可以找到一个符合这个性质的分类方案。

具体的，对于两个同类相邻点没有被同时选择的情况，我们是可以正常处理的。我们只需要讨论两个同类相邻点被同时选择的情况。Usage 1 的本质是检查是否存在一个颜色为 c 且被选中的点和一个未被选中的点相邻，所以我们在这里强调每个点都需要和一个不同类的点相邻。

考虑此时 Usage 1 的工作机制是否正常。由于同时被选择的两个相邻同类点本身的颜色就是不同的，那么即使选出的 x 个同类点之间可能连边，但是它们形成的同色连通块必然还是 x 个（和独立集的情况相同）。这个道理对交互库的返回值也是类似的。经过简单的分析就可以得到结论：Usage 1 的判断不会因此产生影响。

既然我们需要保证一条边连接的两个点颜色不同，那么不妨先将原图的所有同色连通块缩成一个单点，那么在缩点后的新图上，根据性质，一个分类方案只需要满足“每个点都需要和一个不同类的点相邻”。为了做到这一点，只需要找到新图的任意一棵生成树，在这棵树上黑白染色即可。

接下来的问题是找到原图中的所有同色连通块，并将其缩点。这个问题实际上就是本题的 50% 部分分。

我们此时不妨对每个点求出与其颜色相同的相邻点，据此即可通过并查集缩点。接下来给出询问的另一个用途。

Usage 2：对于某个点 x，以及和它相邻的若干个点形成的集合 S（这个集合不需要是和 x 相邻的所有点），为了检测这个集合中是否存在和 x 同样颜色的点，我们可以进行两次询问：

询问 1：令 S 中的所有点颜色不变，其余所有点颜色均变为 N，求出此时的同色连通块数量 x；

询问 2：在询问 1 的基础上，令 x 点的颜色不变，求出此时的同色连通块数量 y。

那么，如果 S 中不存在和 x 颜色相同的点，那么 x 本身形成一个同色连通块，也就是 y = x + 1；否则，x 必然会和加入至少一个同色相邻点的连通块中，也就是 y \leq x。据此进行判断即可。

Usage 2 同样可以进行二分，但是每次操作需要两次询问，预计开销将会到达 2 N \log N，显然无法通过此题。考虑如何减少一个询问。

注意到一个事实：对于每条边连接的两个点，只需要在某个点计算颜色是否相同即可。这启发我们钦定每个点的计算顺序，进一步得到接下来的增量算法：

首先，随便找一个点，将其放在某个不断扩大的图中，下面称其为增量图。另外，对增量图的每个同色连通块，实时维护一个互不相同的编号。接下来，不断进行下面的操作，直到每个点都被加入到增量图中：

选择一个没有被加入增量图的点 x，并尝试将其加入到增量图中。此时，找到在原图中和 x 相邻，且加入到增量图中的点，并将这些点所在的同色连通块的编号提出。接下来，考虑从 x 和其中哪些连通块存在同样的颜色，并将它们合并起来（如果没有同色连通块，新开一个编号即可）。每条边连接的两个点的同色情况将会在较晚加入增量图的点中统计，故最终形成的同色连通块和原图的同色连通块一致。

在增量图上，Usage 2 的第一步可以直接通过同色联通块的编号算出，故可以省去第一个询问。

我们尝试估计出上面的方案所需的询问次数。首先，假设连通块在第 i 个点加入时的颜色数为 c_{i}，且假设 c_1 = 0, c_{n+1} = C。那么此时有 c_{i+1} \leq c_i + 1，自然可以得到 c_{i} \leq i - 1。对于每个点而言，其每次会进行一次失败的二分试探，而对于每次成功试探，将会进行一次完整的二分，那么贡献的询问次数的上界就是 1 + \sum_{l = c_{i+1}}^{c_i} (\lceil \log l \rceil + 1)，在这个点和每个同色连通块都相邻时取得上界。进行求和后，总共所需的询问次数不会超过：（令 P_i = \sum_{l=1}^{i} (\lceil \log l \rceil + 1)）

\begin{aligned} &\sum_{i=1}^{N} [1 + \sum_{l = c_{i+1}}^{c_i} (\lceil \log l \rceil + 1)]\\ \leq \ & \sum_{i=1}^{N} [1 + \sum_{l = c_{i+1} + 1}^{c_i + 1} (\lceil \log l \rceil + 1)]\\ =\ & N + \sum_{i=1}^{N} P_{c_i + 1} - P_{c_{i+1}}\\ =\ & N - P_{C} + P_{c_0} + \sum_{i=1}^{N} P_{c_i+1} - P_{c_{i}}\\ =\ & N - P_{C} + \sum_{i=1}^{N} (\lceil \log (c_{i} + 1) \rceil + 1)\\ \leq\ & N - P_{C} + \sum_{i=1}^{N} (\lceil \log i \rceil + 1)\\ =\ & N + \sum_{i=C+1}^{N} (\lceil \log i \rceil + 1) \end{aligned}

我们就得到了前半部分操作数的一个上界。而在得到 C 个同色连通块后，我们进行缩点并通过二分图的方案求解，此时将会带来额外的 2N + \sum_{i=1}^{C} (\lceil \log i \rceil + 1) 个操作。那么可以得到操作数的总上界为：

\begin{aligned} &N + \sum_{i=C+1}^{N} (\lceil \log i \rceil + 1) + 2N + \sum_{i=1}^{C} (\lceil \log i \rceil + 1)\\ =\ & 3 N + \sum_{i=1}^{N} (\lceil \log i \rceil + 1)\\ \leq\ & 3 N + N \lceil \log N \rceil \end{aligned}

在 N = 250 时，这个上界恰好为 2750，可以通过。事实上，真实的上界在 N = 250 时等于 2745。

实现时注意所有颜色相同的 corner case。

#include <vector>
#include <numeric>
#include <cassert>
#include <algorithm>
using namespace std;

int perform_experiment(vector<int> E);

vector<int> g[250], ng[250];
int P[250], Q[250], c, n;
int fa[250];

int getf(int x) {
  return x == fa[x] ? x : fa[x] = getf(fa[x]);
}

// count all components with sphinx's color
int sphinx_components(const vector<int> &Q) {
  int res = 0;
  iota(fa, fa + n, 0);
  for (int i = 0; i < n; i ++) if (Q[i] == n) {
    ++ res;
    for (auto j: g[i]) if (Q[i] == Q[j]) {
      int u = getf(i), v = getf(j);
      if (u != v)
        -- res, fa[u] = v;
    }
  }
  return res;
}

// assume that all groups of -1 are different from their sublings
// count components other than -1
int assume_components(const vector<int> &Q) {
  int res = n - count(Q.begin(), Q.end(), -1);
  iota(fa, fa + n, 0);
  for (int i = 0; i < n; i ++) if (Q[i] != -1)
    for (auto j: g[i]) if (Q[i] == Q[j]) {
      int u = getf(i), v = getf(j);
      if (u != v)
        -- res, fa[u] = v;
    }
  return res;
}

bool check_ng(const vector<int> &v, int l, int r, int col) {
  vector<int> query(n);
  vector<bool> app(c);
  for (int i = l; i <= r; i ++)
    app[v[i]] = true;
  for (int i = 0; i < n; i ++)
    query[i] = (app[P[i]] ? -1 : col);
  return perform_experiment(query) != assume_components(query) + (r - l + 1);
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
  int m = X.size(); n = N;
  for (int i = 0; i < m; i ++) {
    int x = X[i], y = Y[i];
    g[x].push_back(y);
    g[y].push_back(x);
  }
  iota(P, P + n, 0);
  fill(Q, Q + n, -1);
  // coloring
  for (int x = 0; x < n; x ++) {
    vector<int> adj_colors;
    for (auto v: g[x])
      if (v < x)
        adj_colors.push_back(P[v]);
    sort(adj_colors.begin(), adj_colors.end());
    adj_colors.erase(unique(adj_colors.begin(), adj_colors.end()), adj_colors.end());
    int L = 0, m = adj_colors.size();

    auto check = [&] (int l, int r) {
      vector<bool> app(n);
      for (int i = l; i <= r; i ++)
        app[adj_colors[i]] = true;
      vector<int> query(n, n);
      query[x] = -1;
      for (int i = 0; i < n; i ++) if (P[i] != -1 && app[P[i]])
        query[i] = -1;
      return sphinx_components(query) + (r - l + 1) + 1 != perform_experiment(query);
    };

    while (L < m && check(L, m - 1)) {
      int l = L, r = m - 1, rl = m - 1;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(L, mid))
          rl = mid, r = mid - 1;
        else
          l = mid + 1;
      }
      for (int i = 0; i < n; i ++) if (P[i] == adj_colors[rl])
        P[i] = x;
      L = rl + 1;
    }
  }
  // renumber colors
  {
    vector<int> G;
    for (int i = 0; i < n; i ++)
      G.push_back(P[i]);
    sort(G.begin(), G.end());
    G.erase(unique(G.begin(), G.end()), G.end());
    c = G.size();
    for (int i = 0; i < n; i ++)
      P[i] = lower_bound(G.begin(), G.end(), P[i]) - G.begin();
  }
  // all with same color
  if (c == 1) {
    for (int i = 0; i < n; i ++) {
      vector<int> query(n, -1);
      query[0] = i;
      if (perform_experiment(query) == 1)
        return vector<int>(n, i);
    }
    assert(false);
  }
  for (int i = 0; i < n; i ++)
    for (auto j: g[i])
      ng[P[i]].push_back(P[j]), ng[P[j]].push_back(P[i]);
  vector<int> black, white;
  vector<bool> vis(n);
  auto dfs = [&] (auto self, int x, int col) -> void {
    (col ? black : white).push_back(x);
    vis[x] = true;
    for (auto y: ng[x]) if (!vis[y])
      self(self, y, !col);
  };
  dfs(dfs, 0, 0);
  for (auto v: {black, white}) {
    for (int i = 0; i < n; i ++) {
      int L = 0;
      vector<int> new_v;
      for (auto e: v) if (Q[e] == -1)
        new_v.push_back(e);
      swap(v, new_v);
      int m = v.size();
      while (L < m && check_ng(v, L, m - 1, i)) {
        int l = L, r = m - 1, rl = m - 1;
        while (l <= r) {
          int mid = (l + r) >> 1;
          if (check_ng(v, L, mid, i))
            rl = mid, r = mid - 1;
          else
            l = mid + 1;
        }
        Q[v[rl]] = i;
        L = rl + 1;
      }
    }
  }
  vector<int> ans(n);
  for (int i = 0; i < n; i ++)
    ans[i] = Q[P[i]];
  return ans;
}