oj.uz

Submission #361311

# Submission time Handle Problem Language Result Execution time Memory
361311 2021-01-29T08:43:14 Z Seanliu Furniture (JOI20_furniture) C++14
0 / 100
 13 ms 1132 KB 
#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;
    indeg[i + 1][j]--;
    indeg[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);
}

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';
        rem(y, x);
    }
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Incorrect 13 ms 1132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Incorrect 13 ms 1132 KB Output isn't correct
3 Halted 0 ms 0 KB -