P10433 [JOISC 2024 Day2] 棋盘游戏 题解

Description

有一个供 $K$ 个玩家玩的棋盘游戏。该游戏的棋盘由 $N$ 个编号从 1 到 $N$ 的单元格和 $M$ 条编号从 1 到 $M$ 的路径组成，其中路径 $j$（$1 ≤ j ≤ M$）双向连接着单元格 $U_j$ 和 $V_j$。

棋盘上有两种类型的单元格：重新激活单元格和停止单元格。

这些信息由长度为 $N$ 的字符串 $S$ 给出，$S$ 由 $0$ 和 $1$ 组成，其中 $S$ 的第 $i$ 个字符（$1 ≤ i ≤ N$）是 0 表示单元格 $i$ 是重新激活单元格，是 1 表示单元格 $i$ 是停止单元格。

这个棋盘游戏由编号从 $1$ 到 $K$ 的 $K$ 个玩家进行。每个玩家都有自己的棋子，游戏从每个玩家将其棋子放在特定的单元格上开始。一开始，玩家 $p$（$1 \leq p \leq K$）将其棋子放在单元格 $X_p$ 上。注意，多个玩家的棋子可以放在同一个单元格上。

游戏随着每个玩家轮流进行而进行，从玩家 1 开始，按数字顺序进行。在玩家 $p$ 完成其回合后，玩家 $p + 1$ 开始回合（如果 $p = K$，则玩家 1 开始回合）。每个玩家在其回合上执行以下操作：

1. 选择与其棋子所在的单元格通过一条路径相连的一个单元格，并将其棋子移动到所选择的单元格上。

2. 如果目标单元格是重新激活单元格，则重复步骤 1 并继续其回合。如果目标单元格是停止单元格，则结束其回合。

代表日本参加这个棋盘游戏的包括 JOI 君在内的由 $K$ 名成员组成的团队，正在研究协作策略，以快速征服这个游戏。他们目前正在研究以下问题：

为了将玩家 1 的棋子放置在单元格 $T$ 上，$K$ 名玩家需要的最小总移动次数是多少？即使在回合中途，如果玩家 1 的棋子被放置在单元格 $T$ 上，也认为满足条件。

给定关于游戏棋盘和每个玩家棋子的初始放置位置的信息，编写一个程序来计算每个 $T = 1, 2, \ldots, N$ 对应的问题的答案。

$N,M,K\leq 5\times 10^4$。

Solution

显然 $2\sim k$ 人对答案的贡献只与进行的轮数 $x$ 有关。

设 $f(i,x)$ 表示第 $i$ 个人走 $x$ 轮的最小步数，$F(x)=\sum_{i=2}^{k}{f(i,x)}$。那么 $f(i,x)$ 只有两种可能的贡献：

1. $i$ 先走到一个最近的停止点然后一直跳出去再跳回来。

2. $i$ 走到一个最近的邻域有停止点的停止点然后每次反复横跳。

不妨设 $dis_{1,i}$ 表示 $i$ 走到最近的停止点的距离。第一种贡献很容易得到是 $dis_{1,i}+2(x-1)$。

对于第二种情况，设 $i$ 走到一个邻域有停止点的停止点轮数为 $c$，步数为 $d$。那么如果 $c\leq x$，可以得到贡献是 $d+x-c$。同时由于没多走一轮，步数至少增加一，所以 $d+x-c$ 对于 $c>x$ 的情况也成立。

于是对第二种情况的 $d-c$ 跑 01bfs 即可求出所有 $f(i,x)$ 的值。

设 $G(x,u)$ 表示 $1$ 走恰好 $x$ 轮到 $u$ 的最小步数，则 $ans_u=\min_{x=1}^{n}{\left(F(x)+G(x,u)\right)}$。

---

由于 $f(i,x)$ 形如 $\min(d_1+x,d_2+2x)$，所以 $F(x)$ 一定是一个凸函数，且只有最多 $k$ 段。

那么对于 $k$ 比较小的情况可以找到函数的每段 $y=px+q$，将 $p$ 放到最短路的边权上跑 dijkstra 即可做到 $O(nk\log n)$。

又因为 $x$ 每增大 $1$，$F(x)$ 至少减 $k-1$，要想让答案更优，$G(x,u)$ 也要减少至少 $k-1$，而 $G(x,u)\leq n$，所以只会减少至多 $\frac{n}{k-1}$ 轮。

设 $dis_{3,i}$ 表示 $i$ 走到一个停止点的最小轮数，则能对 $i$ 的答案产生影响的轮数一定在 $\left[dis_{3,i},dis_{3,i}+\frac{n}{k-1}\right]$ 内，对这个进行分层图 bfs 即可做到 $O\left(\frac{n^2}{k}\right)$。

将阈值设为 $\sqrt{\frac{n}{\log n}}$ 时可以得到时间复杂度为 $O\left(n\sqrt{n\log n}\right)$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 5e4 + 5, kLim = 100, kInf = 1e12;

int n, m, k;
int a[kMaxN], dis0[kMaxN], dis1[kMaxN], dis2[kMaxN], ans[kMaxN], f[kMaxN];
bool op[kMaxN];
std::vector<int> G[kMaxN];

void bfs0() {
  std::queue<int> q;
  for (int i = 1; i <= n; ++i) dis0[i] = kInf;
  dis0[a[1]] = 0, q.emplace(a[1]);
  for (; !q.empty();) {
    int u = q.front(); q.pop();
    if (op[u] && u != a[1]) continue;
    for (auto v : G[u]) {
      if (dis0[v] == kInf) {
        dis0[v] = dis0[u] + 1, q.emplace(v);
      }
    }
  }
}

void bfs1() {
  std::queue<int> q;
  for (int i = 1; i <= n; ++i) {
    dis1[i] = kInf;
    bool fl = 0;
    for (auto j : G[i]) fl |= op[j];
    if (fl) dis1[i] = 1, q.emplace(i);
  }
  for (; !q.empty();) {
    int u = q.front(); q.pop();
    for (auto v : G[u]) {
      if (dis1[v] == kInf) {
        dis1[v] = dis1[u] + 1, q.emplace(v);
      }
    }
  }
}

void bfs2() {
  std::deque<int> q;
  for (int i = 1; i <= n; ++i) {
    dis2[i] = kInf;
    bool fl = 0;
    for (auto j : G[i]) fl |= op[j];
    if (op[i] && fl) dis2[i] = 0, q.emplace_back(i);
  }
  for (; !q.empty();) {
    int u = q.front(); q.pop_front();
    for (auto v : G[u]) {
      int dv = dis2[u] + 1 - op[u];
      if (dv < dis2[v]) {
        dis2[v] = dv;
        if (op[u]) q.emplace_front(v);
        else q.emplace_back(v);
      }
    }
  }
}

void getf() {
  static int g[kMaxN] = {0};
  for (int c = 2; c <= k; ++c) {
    int x = a[c];
    int p = std::min(std::max<int>(dis2[x] - dis1[x] + 3, 1), n + 1);
    f[1] += dis1[x] - 2, f[p] -= dis1[x] - 2, f[p] += dis2[x];
    g[1] += 2, g[p] -= 2, g[p] += 1;
  }
  for (int i = 1; i <= n; ++i) f[i] += f[i - 1], g[i] += g[i - 1];
  for (int i = 1; i <= n; ++i) f[i] += i * g[i];
}

namespace Sub1 {
void getans(int k, int b) {
  static int dis[kMaxN];
  static bool vis[kMaxN] = {0}, vv[kMaxN] = {0};
  std::priority_queue<std::pair<int, int>> q;
  for (int i = 1; i <= n; ++i) dis[i] = kInf, vis[i] = vv[i] = 0;
  dis[a[1]] = 0, q.emplace(0, a[1]);
  for (; !q.empty();) {
    int u = q.top().second; q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto v : G[u]) {
      int w = 1 + k * (op[u] && u != a[1]);
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w, q.emplace(-dis[v], v);
        vv[v] = (vv[u] | (w > 1));
      }
    }
  }
  for (int i = 1; i <= n; ++i)
    if (vv[i]) ans[i] = std::min(ans[i], dis[i] + b);
}

void solve() {
  int nowk = -1;
  for (int i = 2; i <= n; ++i) {
    int k = f[i] - f[i - 1];
    if (k != nowk) {
      getans(k, f[i] - i * k);
      nowk = k;
    }
  }
}
} // namespace Sub1

namespace Sub2 {
int lim, dis3[kMaxN], dis4[kMaxN][kMaxN / (kLim - 1) + 5];

void bfs3() {
  std::deque<int> q;
  for (int i = 1; i <= n; ++i) dis3[i] = kInf;
  q.emplace_back(a[1]), dis3[a[1]] = 0;
  for (; !q.empty();) {
    int u = q.front(); q.pop_front();
    int w = (op[u] && u != a[1]);
    for (auto v : G[u]) {
      if (dis3[v] > dis3[u] + w) {
        dis3[v] = dis3[u] + w;
        if (!w) q.emplace_front(v);
        else q.emplace_back(v);
      }
    }
  }
}

void bfs4() {
  std::queue<std::pair<int, int>> q;
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= lim; ++j)
      dis4[i][j] = kInf;
  dis4[a[1]][0] = 0, q.emplace(a[1], 0);
  for (; !q.empty();) {
    auto [u, t] = q.front(); q.pop();
    int w = (op[u] && u != a[1]);
    for (auto v : G[u]) {
      int tv = t + dis3[u] + w - dis3[v];
      if (tv <= lim && dis4[v][tv] > dis4[u][t] + 1) {
        dis4[v][tv] = dis4[u][t] + 1;
        q.emplace(v, tv);
      }
    }
  }
}

void solve() {
  lim = n / (k - 1);
  bfs3(), bfs4();
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= lim; ++j)
      ans[i] = std::min(ans[i], dis4[i][j] + f[dis3[i] + j]);
}
} // namespace Sub2

void dickdreamer() {
  std::cin >> n >> m >> k;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v), G[v].emplace_back(u);
  }
  std::string str;
  std::cin >> str;
  for (int i = 1; i <= n; ++i) op[i] = str[i - 1] - '0';
  for (int i = 1; i <= k; ++i) std::cin >> a[i];
  bfs0(), bfs1(), bfs2(), getf();
  for (int i = 1; i <= n; ++i) ans[i] = dis0[i];
  if (!std::count(op + 1, op + 1 + n, 1)) {
    for (int i = 1; i <= n; ++i) std::cout << ans[i] << '\n';
    return;
  }
  if (k <= kLim) Sub1::solve();
  else Sub2::solve();
  ans[a[1]] = 0;
  for (int i = 1; i <= n; ++i) std::cout << ans[i] << '\n';
}

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