Submission #536354

#	Time	Username	Problem	Language	Result	Execution time	Memory
536354		Monarchuwu	Furniture (JOI20_furniture)	C++17	100 / 100	365 ms	25496 KiB

furniture

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 1111;
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
int m, n;
int c[N][N], id[N][N];

int par[N * N];
int root(int u) { return par[u] < 0 ? u : par[u] = root(par[u]); }
void Union(int u, int v) {
    if ((u = root(u)) == (v = root(v))) return;
    if (par[u] > par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;
}
void Join(int i, int j) {
    for (int k = 0, x, y; k < 4; ++k) {
        x = i + dx[k], y = j + dy[k];
        if (c[x][y]) Union(id[i][j], id[x][y]);
    }
}

queue<pii> q;
void bfs() {
    while (!q.empty()) {
        pii x = q.front(); q.pop();
        if (c[x.ff][x.ss]) continue;
        c[x.ff][x.ss] = 1;
        Join(x.ff, x.ss);

        if (c[x.ff - 1][x.ss + 1]) {
            if (!c[x.ff][x.ss + 1])
                q.emplace(x.ff, x.ss + 1);
            if (!c[x.ff - 1][x.ss])
                q.emplace(x.ff - 1, x.ss);
        }

        if (c[x.ff + 1][x.ss - 1]) {
            if (!c[x.ff][x.ss - 1])
                q.emplace(x.ff, x.ss - 1);
            if (!c[x.ff + 1][x.ss])
                q.emplace(x.ff + 1, x.ss);
        }
    }
}
void build() {
    memset(par, -1, sizeof(par));
    for (int i = 1; i <= m; ++i) {
        c[i][0] = c[i + 1][0] = c[i - 1][n + 1] = c[i][n + 1] = 1;
        Union(id[i][0], id[i + 1][0]);
        Union(id[i - 1][n + 1], id[i][n + 1]);
    }
    for (int j = 1; j <= n; ++j) {
        c[0][j] = c[0][j + 1] = c[m + 1][j - 1] = c[m + 1][j] = 1;
        Union(id[0][j], id[0][j + 1]);
        Union(id[m + 1][j - 1], id[m + 1][j]);
    }

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) {
            cin >> c[i][j];
            if (c[i][j]) q.emplace(i, j), c[i][j] = 0;
        }
    bfs();
}

bool check(int i, int j) {
    return (root(id[m + 1][0]) == root(id[i + 1][j - 1]) && root(id[0][n + 1]) == root(id[i - 1][j + 1]));
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 0; i <= m + 1; ++i)
        for (int j = 0; j <= n + 1; ++j) id[i][j] = i * (n + 2) + j;
    build();

    int qq, i, j; cin >> qq; while (qq--) {
        cin >> i >> j;
        if (!c[i][j]) {
            if (check(i, j)) cout << "0\n";
            else {
                cout << "1\n";
                q.emplace(i, j);
                bfs();
            }
        }
        else cout << "1\n";
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95