Submission #435840

#	Time	Username	Problem	Language	Result	Execution time	Memory
435840		MladenP	Furniture (JOI20_furniture)	C++17	100 / 100	1002 ms	66984 KiB

furniture

#include <bits/stdc++.h>
#define MAXN 1010
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int N, M, C[MAXN][MAXN], vis[MAXN][MAXN];
set<pii> s[2*MAXN];
void clean(int X, int Y) {
    vis[X][Y] = 1;
    s[X+Y].erase({X, Y});
    if(vis[X+1][Y-1]) {
        if(!vis[X+1][Y]) clean(X+1, Y);
        if(!vis[X][Y-1]) clean(X, Y-1);
    } if(vis[X-1][Y+1]) {
        if(!vis[X][Y+1]) clean(X, Y+1);
        if(!vis[X-1][Y]) clean(X-1, Y);
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            cin >> C[i][j];
            if(C[i][j] == 0) s[i+j].insert({i, j});
            else vis[i][j] = 1;
        }
    }
    for(int i = 0; i <= N+1; i++) vis[i][0] = vis[i][M+1] = 1;
    for(int i = 0; i <= M+1; i++) vis[0][i] = vis[N+1][i] = 1;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            if((i == 1 && j == 1) || (i == N && j == M)) continue;
            if(!vis[i][j] && ((vis[i+1][j] && vis[i][j+1]) || (vis[i-1][j] && vis[i][j-1]))) clean(i, j);
        }
    }
    int Q; cin >> Q;
    while(Q--) {
        int X, Y; cin >> X >> Y;
        if(vis[X][Y]) {
            cout << 1 << '\n';
            C[X][Y] = 1;
        } else {
            if(s[X+Y].size() == 1) {
                cout << 0 << '\n';
            } else {
                clean(X, Y);
                cout << 1 << '\n';
            }
        }
    }
    return 0;
}

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