CF325D Reclamation 题解

题意：

给定一个大小为 $r \times c$ 的二维环形网格图，每一行的第 $1$ 格和第 $c$ 格相邻。

现在按照给定的顺序将 $n$ 个格子变成障碍物。

一个格子可以变成障碍的条件为该格子变成障碍后仍然存在一条从第 $1$ 行到第 $r$ 行的路径。

如果一个格子不可以变成障碍，就跳过该操作并且继续处理接下来的格子。路径为四相邻规则。

你需要求出最多可以有多少个格子变成障碍物。

输入格式：

第一行有三个整数 $r,c,n(1 \le r,c \le 3000, 1 \le n \le 3 \times 10^5)$。

接下来 $n$ 行，每行两个正整数 $r_i , c_i$，表示将位于 $r_i $ 行，$c_i$ 列的格子变成障碍物。

输出格式：

输出一个整数表示答案。

如果删掉一格后环不再构成四连通，那么这个点和其他已删除的点将圆柱的侧面截断。

换句话说，此时这个环（或者说曲面）上存在一个由已删除点构成的八连通块。

维护环的连通性十分麻烦。考虑断环为链，然后用并查集维护已删除点的连通性。

这样我们只需要判断删除操作是否会使得 $(x,y)$ 和 $(x,y+c)$ 连通即可。

注意每次删除一个点，要把 $(x,y)$ 和 $(x,y+c)$ 都标记。

时间复杂度 $\mathcal{O}(n\alpha(n) + 2rc)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(2e7 + 15))

char vis[N];
int R, C, f[N], sz[N];
const int dx[] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int id(int x, int y) { return (x - 1) * 2 * C + y; }
bool safe(int &x, int &y)
{
    if(!y) y = C * 2; else if(y == C * 2 + 1) y = 1;
    return (x > 0 && x <= R && vis[id(x, y)]);
}
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int u, int v)
{
    int x = find(u), y = find(v);
    if(sz[x] > sz[y]) swap(x, y);
    sz[y] += sz[x]; f[x] = y;
}
void del(int x, int y)
{
    const int tx = x, ty = y + C;
    for(int i = 0; i < 8; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(safe(a, b)) merge(id(x, y), id(a, b));
        int c = tx + dx[i], d = ty + dy[i];
        if(safe(c, d)) merge(id(tx, ty), id(c, d));
    }
    vis[id(x, y)] = vis[id(tx, ty)] = true;
}
bool check(int x, int y)
{
    const int tx = x, ty = y + C;
    for(int i = 0; i < 8; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(!safe(a, b)) continue;
        for(int j = 0; j < 8; j++)
        {
            int c = tx + dx[j], d = ty + dy[j];
            if(!safe(c, d)) continue;
            if(find(id(a, b)) == find(id(c, d))) return false;
        }
    }
    return true;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int q, res = 0; cin >> R >> C >> q;
    if(C == 1) return cout << "0\n", 0;
    for(int i = 1; i <= R; i++)
        for(int j = 1; j <= C * 2; j++) { f[id(i, j)] = id(i, j), sz[i] = 1; }
    for(int i = 1, x, y; i <= q; i++) {
        cin >> x >> y; if(check(x, y)) { del(x, y), ++res; }
    }
    cout << res << '\n';
    return 0;
}