제출 #1141037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141037		the_coding_pooh	Furniture (JOI20_furniture)	C++20	100 / 100	174 ms	11324 KiB

furniture

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

const int SIZE = 1e3 + 5;

int cnt_depth[2 * SIZE];

bool able[SIZE][SIZE];

int cnt_pa[SIZE][SIZE], cnt_kid[SIZE][SIZE];

void init(int N, int M){
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= M; j++){
            cin >> able[i][j];
            able[i][j] ^= 1;
        }
    }
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= M; j++){
            if(i != 1 || j != 1)
                able[i][j] &= (able[i - 1][j] || able[i][j - 1]);
        }
    }
    for (int i = N; i >= 1; i--){
        for (int j = M; j >= 1; j--){
            if(i != N || j != M)
                able[i][j] &= (able[i + 1][j] || able[i][j + 1]);
        }
    }
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= M; j++){
            cnt_depth[i + j - 2] += able[i][j];
            cnt_pa[i][j] = able[i - 1][j] + able[i][j - 1];
            cnt_kid[i][j] = able[i + 1][j] + able[i][j + 1];
        }
    }
    return;
}

void dfs_pa(int x, int y, int N, int M){
    if(x < 1 || y < 1 || x > N || y > M || !able[x][y])
        return;
    cnt_kid[x][y]--;
    if(cnt_kid[x][y] == 0){
        cnt_depth[x + y - 2]--;
        able[x][y] = 0;
        dfs_pa(x - 1, y, N, M);
        dfs_pa(x, y - 1, N, M);
    }
    return;
}

void dfs_kid(int x, int y, int N, int M){
    if(x < 1 || y < 1 || x > N || y > M || !able[x][y])
        return;
    cnt_pa[x][y]--;
    if(cnt_pa[x][y] == 0){
        cnt_depth[x + y - 2]--;
        able[x][y] = 0;
        dfs_kid(x + 1, y, N, M);
        dfs_kid(x, y + 1, N, M);
    }
    return;
}

int main(){
    cin.tie(0), ios::sync_with_stdio(0);
    int N, M;
    cin >> N >> M;
    init(N, M);
    int Q;
    cin >> Q;
    for (int x, y; Q--;){
        cin >> x >> y;
        if(able[x][y] && cnt_depth[x + y - 2] == 1){
            cout << "0\n";
        }
        else{
            cout << "1\n";
            if(able[x][y]){
                able[x][y] = 0;
                cnt_depth[x + y - 2]--;
                dfs_pa(x - 1, y, N, M);
                dfs_pa(x, y - 1, N, M);
                dfs_kid(x + 1, y, N, M);
                dfs_kid(x, y + 1, N, M);
            }
        }
    }
    uwu
}

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