Submission #784608

#	Time	Username	Problem	Language	Result	Execution time	Memory
784608		makanhulia	Furniture (JOI20_furniture)	C++17	100 / 100	956 ms	99368 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second

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

int n, m;
bool a[1005][1005], check[1005][1005], vis[1005][1005];
set<int> s1[1005], s2[1005];

void dfs1(int x, int y) {
    vis[x][y] = 1;
    if (a[x][y]) return;
    for (int i = 0; i < 2; i++) {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx > n or ty > m) continue;
        if (!vis[tx][ty]) dfs1(tx, ty);
        check[x][y] |= check[tx][ty];
    }
}

void dfs2(int x, int y) {
    check[x][y] = 0;
    s1[y].erase(x), s1[y + 1].erase(x), s2[x].erase(y), s2[x + 1].erase(y);
    int tx = x - 1, ty = y - 1;
    if (tx >= 1 and check[tx][y] and !check[tx][y + 1]) dfs2(tx, y);
    if (ty >= 1 and check[x][ty] and !check[x + 1][ty]) dfs2(x, ty);
    tx = x + 1, ty = y + 1;
    if (tx <= n and check[tx][y] and !check[tx][y - 1]) dfs2(tx, y);
    if (ty <= m and check[x][ty] and !check[x - 1][ty]) dfs2(x, ty);
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    vis[n][m] = 1, check[n][m] = 1;
    dfs1(1, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (check[i][j] and check[i][j - 1]) s1[j].insert(i);
            if (check[i][j] and check[i - 1][j]) s2[i].insert(j);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (!check[x][y]) cout << 1 << "\n";
        else {
            auto it1 = s1[y].upper_bound(x), it2 = s2[x].upper_bound(y);
            if (it1 == s1[y].end() and it2 == s2[x].end()) {
                cout << 0 << "\n";
                continue;
            }
            cout << 1 << "\n";
            dfs2(x, y);
        }
    }
}  

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