oj.uz

Submission #435840

# Submission time Handle Problem Language Result Execution time Memory
435840 2021-06-23T19:19:09 Z MladenP Furniture (JOI20_furniture) C++17
100 / 100
 1002 ms 66984 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1220 KB Output is correct
2 Correct 3 ms 1356 KB Output is correct
3 Correct 4 ms 1484 KB Output is correct
4 Correct 7 ms 1632 KB Output is correct
5 Correct 7 ms 1696 KB Output is correct
6 Correct 9 ms 1776 KB Output is correct
7 Correct 6 ms 1740 KB Output is correct
8 Correct 7 ms 1784 KB Output is correct
9 Correct 6 ms 1740 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1220 KB Output is correct
2 Correct 3 ms 1356 KB Output is correct
3 Correct 4 ms 1484 KB Output is correct
4 Correct 7 ms 1632 KB Output is correct
5 Correct 7 ms 1696 KB Output is correct
6 Correct 9 ms 1776 KB Output is correct
7 Correct 6 ms 1740 KB Output is correct
8 Correct 7 ms 1784 KB Output is correct
9 Correct 6 ms 1740 KB Output is correct
10 Correct 23 ms 3532 KB Output is correct
11 Correct 5 ms 1356 KB Output is correct
12 Correct 842 ms 54624 KB Output is correct
13 Correct 388 ms 45696 KB Output is correct
14 Correct 980 ms 56788 KB Output is correct
15 Correct 1002 ms 57288 KB Output is correct
16 Correct 805 ms 61736 KB Output is correct
17 Correct 869 ms 64992 KB Output is correct
18 Correct 914 ms 63340 KB Output is correct
19 Correct 811 ms 66884 KB Output is correct
20 Correct 694 ms 66892 KB Output is correct
21 Correct 861 ms 66984 KB Output is correct