제출 #680079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680079		stevancv	Furniture (JOI20_furniture)	C++14	5 / 100	5067 ms	54204 KiB

furniture

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define sadd(a, b) a = Add(a, b)
#define smul(a, b) a = Mul(a, b)
using namespace std;
const int N = 1e3 + 2;
const int mod = 1e9 + 7;
int n, m;
bool a[N][N], uni[N][N], x[N][N], y[N][N], z[N][N];
set<pair<int, int>> pos[2 * N];
bool Can(int i, int j) {
    if (i == 1 && j == 1) return 1;
    if (i == n && j == m) return 1;
    if (z[i][j] == 0) return 1;
    return (z[i - 1][j] | z[i][j - 1]) & (z[i + 1][j] | z[i][j + 1]);
}
void Dfs(int i, int j) {
    if (i <= 0 || i > n) return;
    if (j <= 0 || j > m) return;
    z[i][j] = 0;
    pos[i + j].erase({i, j});
    if (!Can(i - 1, j)) Dfs(i - 1, j);
    if (!Can(i, j - 1)) Dfs(i, j - 1);
    if (!Can(i + 1, j)) Dfs(i + 1, j);
    if (!Can(i, j + 1)) Dfs(i, j + 1);
}
void Add(int i, int j) {
    Dfs(i, j);
    for (int l = 2; l <= n + m; l++) {
        if (pos[l].size() == 1) {
            int ii = pos[l].begin()->first;
            int jj = pos[l].begin()->second;
            uni[ii][jj] = 1;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            pos[i + j].insert({i, j});
        }
    }
    for (int l = 2; l <= n + m; l++) {
        if (pos[l].size() == 1) {
            int ii = pos[l].begin()->first;
            int jj = pos[l].begin()->second;
            uni[ii][jj] = 1;
        }
    }
    x[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            x[i][j] |= x[i - 1][j] | x[i][j - 1];
        }
    }
    y[n][m] = 1;
    for (int i = n; i >= 1; i--) {
        for (int j = m; j >= 1; j--) {
            y[i][j] |= y[i + 1][j] | y[i][j + 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            z[i][j] = x[i][j] & y[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 1) Add(i, j);
        }
    }
    int q; cin >> q;
    while (q--) {
        int i, j;
        cin >> i >> j;
        if (uni[i][j] == 1) {
            cout << 0 << en;
        }
        else {
            cout << 1 << en;
            Add(i, j);
        }
    }
    return 0;
}

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