Submission #361314

#	Time	Username	Problem	Language	Result	Execution time	Memory
361314		Seanliu	Furniture (JOI20_furniture)	C++14	100 / 100	3017 ms	26476 KiB

furniture

#include <iostream>
#include <vector>
using namespace std;

const int maxN = 1e3 + 326;
int N, M, levels[maxN * 2], indeg[maxN][maxN], outdeg[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(!isIn[i][j]) return;
    levels[i + j]--;
    isIn[i][j] = false;
    indeg[i + 1][j]--;
    indeg[i][j + 1]--;
    outdeg[i - 1][j]--;
    outdeg[i][j - 1]--;
    if(isIn[i + 1][j] && !indeg[i + 1][j]) rem(i + 1, j);
    if(isIn[i][j + 1] && !indeg[i][j + 1]) rem(i, j + 1);
    if(isIn[i - 1][j] && !outdeg[i - 1][j]) rem(i - 1, j);
    if(isIn[i][j - 1] && !outdeg[i][j - 1]) 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]++;
        outdeg[i - 1][j]++;
        outdeg[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';
        rem(y, x);
    }
}

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