CF 325D Reclamation

2015.01.10 15:45 Sat| 2 visits oi_2015| 2015_刷题日常| Text

Solution

首先将平面复制一份,那么如果从新加入的一点可以八连通扩展到在另一个平面上的对应点,那么就不存在一条符合题意的路径。用并查集维护连通性。注意需要保存修改之前的版本,以便恢复。这一过程可以直接利用vector。

//codeforces 为什么不支持 C++1y QAQ

//为什么我把 dx 和 dy 写错了还过了样例 QAQ

//其实 codeforces 支持 C++0x 已经比许多 OJ 先进十余年了 2333

Code

#include <bits/stdc++.h>
using namespace std;

#define R 3005
#define C 6005

int dx[9] = {0, 1, 1, 0,-1,-1,-1, 0, 1},
    dy[9] = {0, 0, 1, 1, 1, 0,-1,-1,-1};

bool vis[R][C];
int r, c, n, f[R*C];
vector<pair<int,int>> v;

inline int pos(int x, int y)
{
    return 2 * c * (x - 1) + y;
}

int find(int x)
{
    if (x == f[x]) return x;
    v.push_back(make_pair(x, f[x]));
    return f[x] = find(f[x]);
}

void connect(int x, int y)
{
    for (int i = 1; i <= 8; ++i)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx > r) continue;
        if (!ny) ny = c * 2;
        else if(ny == c * 2 + 1) ny = 1;
        if (vis[nx][ny])
        {
            int fx = find(pos(x, y)), fy = find(pos(nx, ny));
            v.push_back({fx, f[fx]}), f[fx] = fy;
        }
    }
}

bool check(int x, int y)
{
    connect(x, y);
    connect(x, y + c);
    if (find(pos(x, y)) == find(pos(x, y + c)))
        return false;
    return true;
}

void clear(vector<pair<int, int>>::iterator it)
{
    if (it == v.end()) return ;
    auto now = it;
    clear(++it);
    f[now->first] = now->second;
}

int main()
{
    cin >> r >> c >> n;
    for (int i = 1; i <= pos(r, c * 2); ++i)
        f[i] = i;
    int ans = 0;
    for (int x, y, i = 1; i <= n; ++i)
    {
        v.clear();
        cin >> x >> y;
        vis[x][y] = vis[x][y + c] = true;
        if (check(x, y))
            ans++;
        else
            vis[x][y] = vis[x][y + c] = false, clear(v.begin());
    }
    cout << ans << endl;
}