Submission #361305

#	Time	Username	Problem	Language	Result	Execution time	Memory
361305		Seanliu	Furniture (JOI20_furniture)	C++14	0 / 100	11 ms	1132 KiB

furniture

#include <iostream>
using namespace std;

const int maxN = 1e3 + 326;
int N, M, levels[maxN * 2], indeg[maxN][maxN], Q, y, x;
bool has[maxN][maxN]; //id of (i, j) is i * M + j
bool isIn[maxN][maxN], vis[maxN][maxN];

void dfs(int i = 1, int j = 1){
    if(i > N || j > M || has[i][j]) return;
    vis[i][j] = true;
    if(i == N && j == M){
        isIn[i][j] = true;
        return;
    }
    if(!vis[i + 1][j]) dfs(i + 1, j);
    if(!vis[i][j + 1]) dfs(i, j + 1);
    isIn[i][j] |= isIn[i + 1][j] | isIn[i][j + 1];
}

void rem(int i, int j){
    if(i > N || j > M || !isIn[i][j] || has[i][j]) return;
    levels[i + j]--;
    isIn[i][j] = false;
    rem(i + 1, j);
    rem(i, j + 1);
}

int main(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) cin >> has[i][j];
    dfs();
    for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) if(isIn[i][j]){
        levels[i + j]++;
        indeg[i + 1][j]++;
        indeg[i][j + 1]++;
    }
    //for(int i = 1; i <= N + M; i++) cout << levels[i] << endl;
    cin >> Q;
    while(Q--){
        cin >> y >> x;
        if(!isIn[y][x]){
            cout << 1 << '\n';
            continue;
        }
        if(levels[y + x] == 1){
            cout << 0 << '\n';
            continue;
        } else cout << 1 <<'\n';
        levels[y + x]--;
        indeg[y + 1][x]--;
        indeg[y][x + 1]--;
        isIn[y][x] = false;
        if(isIn[y + 1][x] && !indeg[y + 1][x]){
            rem(y + 1, x);
        }
        if(isIn[y][x + 1] && !indeg[y][x + 1]){
            rem(y, x + 1);
        }
    }
}

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