P11666 [JOI 2025 Final] 邮局 题解

Description

有一张 $N$ 个节点 $N$ 条边的有向图，节点标号 $1\sim N$。

第 $i$ 条边从节点 $i$ 指向节点 $P_i$（注意，可能出现 $i=P_i$ 的情况），需要花 $1$ 单位时间经过它。

有 $M$ 个包裹，第 $j$（$1\le j\le M$）个包裹要从节点 $A_j$ 运到节点 $B_j$。这些包裹全部从 $0$ 时刻开始运送。

每条边一次只能运送一个包裹。节点可以存储无限多个包裹。

判断：是否能够将所有包裹都运到目的地。如果可以，还要求出到达时间最晚的包裹的到达时刻。

$2\leq N\leq 2\times 10^5,1\leq M\leq 2\times 10^5$。

Solution

首先有个显然的贪心是每个时刻对于每个节点，选择距离终点最远的包裹运送。

暴力做是 $O(NM\log N)$ 的，不太能过。

考虑对于每条边计算最晚经过这条边的时间。

不妨设从早到晚经过 $i\to p_i$ 这条边的所有路径的起点距离 $i$ 为 $d_1,d_2,\ldots,d_k$，设 $t_i$ 表示前 $i$ 个路径经过 $i$ 的最小时间，则满足 $t_i=\max\{d_i,t_{i-1}+1\}$。

于是经过这条边的最小时间有个下界是 $\max_{i=1}^{k}{(d_i+k-i)}$，容易发现 $d$ 递增时最小，此时可以得到一个答案的下界。

设经过 $i\to p_i$ 这条边的下界为 $w_i$，可以证明每个下界都能取得到。

证明

根据上面的贪心策略，经过 $i\to p_i$ 的路径在到达 $i$ 之前只会内部出现阻挡，终点在 $i$ 的子树内的点由于距离终点一定会在经过 $i$ 的路径后通行。

由于只会内部阻挡，所以可以先不考虑阻挡，把它们都走到 $i$ 之后再考虑阻挡的事情，而这得到的就是上面的下界。

对于树的情况用线段树合并维护上面的下界即可。

对于基环树，考虑断环为链，然后把每个基环树按照链的顺序复制两遍，并放到原先的后面。

对于一个 $a_i,b_i$ 的路径，如果 $a_i\to b_i$ 不经过断边，就加入 $(a_i,b_i)$ 和 $(a_i+n,b_i+n)$。否则加入 $(a_i,b_i+n)$ 和 $(a_i+n,root)$。

然后对每个基环树的 $root$ 跑树的做法即可。

时间复杂度：$O((N+M)\log N)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 4e5 + 5, kMaxT = kMaxN * 40;

struct Node {
  int ls, rs, mx, cnt;
} t[kMaxT];

int n, m, cntc, sgt_cnt, ans;
int p[kMaxN], a[kMaxN], b[kMaxN], bel[kMaxN], pos[kMaxN];
int dfn[kMaxN], sz[kMaxN];
int rt[kMaxN], dep[kMaxN], onc[kMaxN];
std::vector<int> G[kMaxN], circ[kMaxN];
std::vector<std::pair<int, int>> vec[kMaxN];

void pushup(int x) {
  t[x].cnt = t[t[x].ls].cnt + t[t[x].rs].cnt;
  t[x].mx = std::max(t[t[x].ls].mx + t[t[x].rs].cnt, t[t[x].rs].mx);
  if (!t[x].cnt) t[x].mx = 0;
}

int merge(int x, int y, int l, int r) {
  if (!x || !y) return x + y;
  if (l == r) {
    t[x].cnt += t[y].cnt, t[x].mx = l + t[x].cnt - 1;
    if (!t[x].cnt) t[x].mx = 0;
    return x;
  }
  int mid = (l + r) >> 1;
  t[x].ls = merge(t[x].ls, t[y].ls, l, mid);
  t[x].rs = merge(t[x].rs, t[y].rs, mid + 1, r);
  pushup(x);
  return x;
}

void update(int &x, int l, int r, int ql, int v) {
  if (!x) x = ++sgt_cnt;
  if (l == r) {
    t[x].cnt += v, t[x].mx = l + t[x].cnt - 1;
    if (!t[x].cnt) t[x].mx = 0;
    return;
  }
  int mid = (l + r) >> 1;
  if (ql <= mid) update(t[x].ls, l, mid, ql, v);
  else update(t[x].rs, mid + 1, r, ql, v);
  pushup(x);
}

void getcirc() {
  static int vis[kMaxN] = {0};
  for (int i = 1; i <= n; ++i) {
    if (vis[i]) continue;
    static int stk[kMaxN];
    int top = 0;
    vis[i] = i, stk[++top] = i;
    for (int j = p[i];; j = p[j]) {
      stk[++top] = j;
      if (vis[j]) break;
      else vis[j] = i;
    }
    if (vis[stk[top]] == i) {
      ++cntc;
      for (int j = top; j == top || stk[j] != stk[top]; --j)
        circ[cntc].emplace_back(stk[j]), onc[stk[j]] = cntc;
      std::reverse(circ[cntc].begin(), circ[cntc].end());
      for (int i = 0; i < circ[cntc].size(); ++i) pos[circ[cntc][i]] = i + 1;
      // for (auto x : circ[cntc]) std::cerr << x << ' ';
      // std::cerr << '\n';
    }
  }
}

/*
4 5
1 5
2 5
3 5
4 5
1 5
2 5
3 5
*/

void build() {
  for (int i = 1; i <= n; ++i) {
    onc[i + n] = onc[i];
    if (!onc[i]) {
      G[p[i]].emplace_back(i), G[p[i] + n].emplace_back(i + n);
    }
  }
  for (int i = 1; i <= cntc; ++i) {
    for (int j = 0; j + 1 < circ[i].size(); ++j) {
      G[circ[i][j + 1]].emplace_back(circ[i][j]);
      G[circ[i][j + 1] + n].emplace_back(circ[i][j] + n);
      // std::cerr << circ[i][j + 1] << ' ' << circ[i][j] << '\n';
      // std::cerr << circ[i][j + 1] + n << ' ' << circ[i][j] + n << '\n';
    }
    G[circ[i][0] + n].emplace_back(circ[i].back());
    // std::cerr << circ[i][0] + n << ' ' << circ[i].back() << '\n';
  }
}

void upd(int a, int b) {
  // std::cerr << "??? " << a << ' ' << b << '\n';
  vec[a].emplace_back(a, 1), vec[b].emplace_back(a, -1);
}

void dfs1(int u, int rt) {
  static int cnt = 0;
  bel[u] = rt, dfn[u] = ++cnt, sz[u] = 1;
  for (auto v : G[u]) {
    if (onc[v]) continue;
    dfs1(v, rt);
    sz[u] += sz[v];
  }
}

void dfs2(int u, int fa) {
  dep[u] = dep[fa] + 1;
  for (auto v : G[u]) {
    assert(v != fa);
    dfs2(v, u);
    rt[u] = merge(rt[u], rt[v], 1, 2 * n);
  }
  for (auto [x, v] : vec[u]) update(rt[u], 1, 2 * n, dep[x], v);
  // std::cerr << t[rt[u]].cnt << ' ' << t[rt[u]].mx << '\n';
  if (t[rt[u]].cnt) {
    ans = std::max(ans, t[rt[u]].mx - dep[u] + 1);
  }
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> p[i];
  getcirc(), build();
  // for (int i = 1; i <= cntc; ++i) dfs1(circ[i].back() + n, circ[i].back() + n);
  for (int i = 1; i <= n; ++i)
    if (onc[i]) dfs1(i, i);
  std::cin >> m;
  for (int i = 1; i <= m; ++i) {
    std::cin >> a[i] >> b[i];
    // if (onc[a[i]] && !onc[b[i]]) return void(std::cout << "-1\n");
    // if (onc[a[i]] && onc[b[i]] && onc[a[i]] != onc[b[i]]) return void(std::cout << "-1\n");
    // if (!onc[a[i]] && onc[b[i]] && onc[bel[a[i]]] != onc[bel[b[i]]])
    // std::cerr << a[i] << ' ' << bel[a[i]] << ' ' << onc[bel[a[i]]] << onc[b[i]] << '\n';
    if (onc[b[i]] && onc[bel[a[i]]] != onc[b[i]]) return void(std::cout << "-1\n");
    if (!onc[b[i]] && (dfn[a[i]] < dfn[b[i]] || dfn[a[i]] > dfn[b[i]] + sz[b[i]] - 1)) return void(std::cout << "-1\n");
    int pa = pos[bel[a[i]]], pb = pos[bel[b[i]]];
    if (pa <= pb) {
      upd(a[i], b[i]), upd(a[i] + n, b[i] + n);
    } else if (pa > pb) {
      upd(a[i], b[i] + n), upd(a[i] + n, circ[onc[bel[a[i]]]].back() + n);
    }
  }
  for (int i = 1; i <= cntc; ++i) dfs2(circ[i].back() + n, 0);
  std::cout << ans << '\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;
}