P9170 [省选联考 2023] 填数游戏 题解

Description

众所周知，Alice 和 Bob 是一对好朋友。今天，他们约好一起玩游戏。

一开始，他们各自有一张空白的纸条。接下来，他们会在纸条上依次写 $n$ 个 $[1,m]$ 范围内的正整数。等 Alice 写完，Bob 在看到 Alice 写的纸条之后开始写他的纸条。

Alice 需要保证她写下的第 $i$ 个数在集合 $S_{i}$ 中，Bob 需要保证他写下的第 $i$ 个数在集合 $T_{i}$ 中。题目保证 $1 \leq\left|S_{i}\right|,\left|T_{i}\right| \leq 2$ 。

Alice 喜欢相同，因此，她希望她写下的数与 Bob 写下的数对应位置相同的个数尽量多。Bob 喜欢不同，因此，他希望他写下的 $n$ 个数 $b_{1}, \ldots, b_{n}$ 互不相同。在此基础上，Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。

即设 Alice 写下的数为 $a_{1}, \ldots, a_{n}$，Bob 写下的数为 $b_{1}, \ldots, b_{n}$，记 $X$ 为满足 $1 \leq i \leq n, a_{i}=b_{i}$ 的下标 $i$ 的个数，则

• Alice 希望最大化 $X,$
• Bob 在保证 $b_{1}, \ldots, b_{n}$ 互不相同的前提下希望最小化 $X$。

你首先想知道 Bob 能否保证他写下的 $n$ 个数互不相同。如果 Bob 能够做到，你想知道在双方均采取最优策略的前提下 $X$ 的值会是多少。

$n,m\leq 10^6,\sum n,\sum m\leq 1.5\times 10^6$。

Solution

这题 Bob 在看到 Alice 写的纸条之后才开始写他的纸条！！

先做特殊性质 A。这个就是让你判断 $b_1,\dots,b_n$ 能否互不相同。

考虑把所有 $T_{i,0}$ 和 $T_{i,1}$ 连边（如果 $|T|=1$，就连一条 $T_{i,0}$ 的自环），题目就转化为将一个图中的边定向，使得每个点的入度不超过 $1$。

容易发现对于每个连通块，如果边数大于点数就一定不合法，否则这个连通块是个树或者基环树，一定合法。

---

然后考虑怎么对一个基环树求答案。

容易发现基环树除掉环的边的方向是定好的，只有环上的边有两种可能。设环的大小为 $k$。

所以 Alice 就只要在这 $k$ 条边对应的 $k$ 个集合中每个集合选一个数，使得两种方向答案的 $\min$ 值最大。

首先对于 $|S_i\cap T_i|=0$ 的边，显然没有贡献。$|S_i\cap T_i|=1$ 的边，肯定选择那个交的数，这相当于已经确定了选的数。$|S_i\cap T_i|=2$ 的边，就只能对于两种方向的一种产生贡献。

设 $c_u$ 表示已经确定的数中第一种方向已有的贡献，$c_u$ 表示已经确定的数中第二种方向已有的贡献，$c$ 表示待确定的集合数量。

那么答案就是：

$$\max_{i=0}^{c}{\left\{\min\{c_u+i,c_v+c-i\}\right\}}$$

这个暴力求就行了。

这一部分的时间复杂度：$O(n)$。

---

然后考虑树的情况。

显然定向方式就是选定一个点作为根的外向树。

对于交为 $1$ 的边 $u\to v$，如果 $u$ 是交的数，那么根一定在 $v$ 的子树里，否则根一定在 $v$ 的子树外。

这一部分的贡献可以用 dfs 序上差分维护。

设 $f_i$ 表示以 $i$ 为根的答案。

然后题目转化为对于所有交为 $2$ 的边 $u\to v$，要选择把 $v$ 子树内或子树外的 $f$ 全加一，使得最后 $\min\{f_1,\dots,f_n\}$ 最大。

观察可知如果两个点他们要将 $f$ 加一的集合不交，则把这两个集合都换成原来的补集一定更优。

所以对于两个点 $u,v$，如果 $u$ 是 $v$ 的祖先，那么不能出现 $u$ 选子树外和 $v$ 选子树内的情况。如果 $u$ 不是 $v$ 祖先，那么不能出现 $u$ 和 $v$ 都选子树外。

于是根据这两个性质可以得到选子树的点一定构成一个到根的链，然后 dfs 一边用线段树维护答案即可。

这一部分的时间复杂度：$O(n\log n)$。

所以总的时间复杂度就是 $O(n\log n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

namespace FASTIO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf;
char getc() {
  return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> bool read(T &x) {
  x = 0; int f = 0; char ch = getc();
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getc();
  while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = getc();
  x = (f ? -x : x); return 1;
}
template<typename A, typename ...B> bool read(A &x, B &...y) { return read(x) && read(y...); }
 
char obuf[1 << 21], *o1 = obuf, *o2 = obuf + (1 << 21) - 1;
void flush() { fwrite(obuf, 1, o1 - obuf, stdout), o1 = obuf; }
void putc(char x) { *o1++ = x; if (o1 == o2) flush(); }
template<class T> void write(T x) {
  if (!x) putc('0');
  if (x < 0) x = -x, putc('-');
  char c[40]; int tot = 0;
  while (x) c[++tot] = x % 10, x /= 10;
  for (int i = tot; i; --i) putc(c[i] + '0');
}
void write(char x) { putc(x); }
void write(char *x) { while (*x) putc(*x++); }
void write(const char *x) { while (*x) putc(*x++); }
template<typename A, typename ...B> void write(A x, B ...y) { write(x), write(y...); }
struct Flusher {
  ~Flusher() { flush(); }
} flusher;
} // namespace FASTIO
using FASTIO::read; using FASTIO::putc; using FASTIO::write;

const int kMaxN = 1e6 + 5;

int n, m;
int cnt[kMaxN], fa[kMaxN], sz[kMaxN], cnted[kMaxN];
std::vector<int> s[kMaxN], t[kMaxN];
std::vector<std::pair<int, int>> G[kMaxN];

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

void unionn(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx != fy) {
    fa[fx] = fy, sz[fy] += sz[fx], cnted[fy] += cnted[fx];
  }
  ++cnted[fy];
}

void addedge(int u, int v, int id) {
  G[u].emplace_back(v, id), unionn(u, v);
  if (u != v) G[v].emplace_back(u, id);
}

namespace Cycle {
int res, p[kMaxN], pid[kMaxN], dep[kMaxN];
bool vis[kMaxN], onc[kMaxN];
std::vector<int> circ, circ_v;

void clear() {
  std::fill_n(vis + 1, m, 0);
  std::fill_n(onc + 1, m, 0);
  std::fill_n(p + 1, m, 0);
}

void dfs1(int u, int fa, int faid) {
  p[u] = fa, dep[u] = dep[fa] + 1, vis[u] = 1;
  for (auto [v, id] : G[u]) {
    if (id == faid) continue;
    if (!vis[v]) {
      pid[v] = id, dfs1(v, u, id);
    } else if (dep[u] >= dep[v]) {
      for (int i = u; i != v; i = p[i]) {
        circ.emplace_back(pid[i]);
        circ_v.emplace_back(i);
        onc[i] = 1;
      }
      circ.emplace_back(id), onc[v] = 1, circ_v.emplace_back(v);
    }
  }
}

void dfs2(int u, int fa) {
  for (auto [v, id] : G[u]) {
    if (v == fa || onc[v]) continue;
    res += (v == s[id][0] || v == s[id].back());
    dfs2(v, u);
  }
}

int solve(int rt) {
  res = 0, circ.clear(), circ_v.clear(), dfs1(rt, 0, 0);
  for (auto x : circ_v) dfs2(x, 0);
  assert(circ.size() == circ_v.size());
  int cu = 0, cv = 0, c = 0;
  for (int i = 0; i < circ.size(); ++i) {
    if (cnt[circ[i]] == 1) {
      if (circ_v[i] == s[circ[i]][0] || circ_v[i] == s[circ[i]].back()) ++cu;
      else ++cv;
    } else if (cnt[circ[i]] == 2) {
      ++c;
    }
  }
  if (circ.size() == 1) c *= 2;
  return res + (abs(cu - cv) <= c ? (cu + cv + c) / 2 : std::min(cu, cv) + c);
}
} // namespace Cycle

namespace Tree {
struct SGT {
  int mi[kMaxN * 4], tag[kMaxN * 4];

  void pushup(int x) {
    mi[x] = std::min(mi[x << 1], mi[x << 1 | 1]);
  }

  void addtag(int x, int v) {
    mi[x] += v, tag[x] += v;
  }

  void pushdown(int x) {
    if (!tag[x]) return;
    addtag(x << 1, tag[x]), addtag(x << 1 | 1, tag[x]);
    tag[x] = 0;
  }

  void build(int x, int l, int r) {
    mi[x] = tag[x] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  }

  void update(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql) {
      return;
    } else if (l >= ql && r <= qr) {
      return addtag(x, v);
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    update(x << 1, l, mid, ql, qr, v), update(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }
} sgt;

int res, dfnc;
int dfn[kMaxN], sz[kMaxN];

void dfs1(int u, int fa) {
  dfn[u] = ++dfnc, sz[u] = 1;
  for (auto [v, id] : G[u]) {
    if (v == fa) continue;
    dfs1(v, u);
    sz[u] += sz[v];
  }
}

void dfs2(int u, int fa) {
  for (auto [v, id] : G[u]) {
    if (v == fa) continue;
    if (cnt[id] == 1) {
      if (v == s[id][0] || v == s[id].back()) {
        sgt.update(1, 1, dfnc, 1, dfn[v] - 1, 1), sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, 1);
      } else {
        sgt.update(1, 1, dfnc, dfn[v], dfn[v] + sz[v] - 1, 1);
      }
    } else if (cnt[id] == 2) {
      sgt.update(1, 1, dfnc, 1, dfn[v] - 1, 1), sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, 1);
    }
    dfs2(v, u);
  }
}

void dfs3(int u, int fa) {
  res = std::max(res, sgt.mi[1]);
  for (auto [v, id] : G[u]) {
    if (v == fa) continue;
    if (cnt[id] == 2) {
      sgt.update(1, 1, dfnc, 1, dfn[v] - 1, -1);
      sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, -1);
      sgt.update(1, 1, dfnc, dfn[v], dfn[v] + sz[v] - 1, 1);
    }
    dfs3(v, u);
    if (cnt[id] == 2) {
      sgt.update(1, 1, dfnc, 1, dfn[v] - 1, 1);
      sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, 1);
      sgt.update(1, 1, dfnc, dfn[v], dfn[v] + sz[v] - 1, -1);
    }
  }
}

int solve(int rt) {
  res = dfnc = 0;
  dfs1(rt, 0);
  sgt.build(1, 1, dfnc);
  dfs2(rt, 0), dfs3(rt, 0);
  return res;
}
} // namespace Tree

void dickdreamer() {
  read(n, m);
  for (int i = 1; i <= m; ++i) {
    G[i].clear();
    fa[i] = i, sz[i] = 1, cnted[i] = 0;
  }
  Cycle::clear();
  for (int i = 1; i <= n; ++i) {
    int c;
    read(c);
    s[i].clear();
    for (int j = 1; j <= c; ++j) {
      int x;
      read(x);
      s[i].emplace_back(x);
    }
  }
  for (int i = 1; i <= n; ++i) {
    int c;
    read(c);
    cnt[i] = 0, t[i].clear();
    for (int j = 1; j <= c; ++j) {
      int x;
      read(x);
      t[i].emplace_back(x);
      for (auto y : s[i]) cnt[i] += (x == y);
    }
    if (c == 1) cnt[i] *= 2;
    if (c == 1) addedge(t[i][0], t[i][0], i);
    else addedge(t[i][0], t[i][1], i);
  }
  int ans = 0;
  for (int i = 1; i <= m; ++i) {
    if (i == find(i)) {
      if (cnted[i] > sz[i]) return void(write("-1\n"));
      else if (cnted[i] == sz[i]) ans += Cycle::solve(i);
      else ans += Tree::solve(i);
    }
  }
  write(ans, '\n');
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  int T = 1;
  read(T);
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}