oj.uz

Submission #721535

# Submission time Handle Problem Language Result Execution time Memory
721535 2023-04-11T03:52:52 Z joelgun14 Furniture (JOI20_furniture) C++17
100 / 100
 714 ms 21708 KB 
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    // tiap diagonal simpan
    // update neighbor bisa visit atau ga
    // kalo misal only node to be able to visit, berarti ga boleh
    // kalo bukan only node yg bisa visit, then absolutely fine
    // cek diagonal ada yg bs atau ga
    int cnt[n + m + 5];
    memset(cnt, 0, sizeof(cnt));
    int grid[n + 1][m + 1];
    bool src[n + 1][m + 1], tgt[n + 2][m + 2];
    memset(src, 0, sizeof(src));
    memset(tgt, 0, sizeof(tgt));
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> grid[i][j];
    src[1][1] = tgt[n][m] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(!grid[i][j])
                src[i][j] |= src[i - 1][j] | src[i][j - 1];
        }
    }
    for(int i = n; i >= 1; --i) {
        for(int j = m; j >= 1; --j) {
            if(!grid[i][j]) {
                tgt[i][j] |= tgt[i + 1][j] | tgt[i][j + 1];
            }
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(src[i][j] && tgt[i][j])
                ++cnt[i + j];
        }
    }
    //for(int i = 2; i <= n + m; ++i) {
    //    cout << cnt[i] << " ";
    //}
    cout << endl;
    int q;
    cin >> q;
    int vis[n + 1][m + 1];
    memset(vis, -1, sizeof(vis));
    for(int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        if(cnt[x + y] == 1 && src[x][y] && tgt[x][y]) {
            cout << 0 << endl;
            continue;
        }
        else {
            // hapus node sekarang dr cnt, dan update neighboring nodes
            queue<pair<int, int>> q;
            q.push({x - 1, y});
            q.push({x, y - 1});
            grid[x][y] = 1;
            if(src[x][y] && tgt[x][y])
                --cnt[x + y];
            src[x][y] = 0, tgt[x][y] = 0;
            while(!q.empty()) {
                int a = q.front().first, b = q.front().second;
                q.pop();
                if(vis[a][b] == i || a < 1 || b < 1 || grid[a][b])
                    continue;
                vis[a][b] = i;
                // change tgt
                int oldtgt = tgt[a][b];
                int ntgt = tgt[a + 1][b] | tgt[a][b + 1];
                if(oldtgt == ntgt)
                    continue;
                // beda berarti update previous jg
                if(oldtgt && src[a][b])
                    --cnt[a + b];
                tgt[a][b] = ntgt;
                q.push({a - 1, b});
                q.push({a, b - 1});
            }
            q.push({x + 1, y});
            q.push({x, y + 1});
            while(!q.empty()) {
                int a = q.front().first, b = q.front().second;
                q.pop();
                if(a > n || b > m || grid[a][b] || vis[a][b] == i)
                    continue;
                vis[a][b] = i;
                // change tgt
                int old = src[a][b];
                int ne = src[a - 1][b] | src[a][b - 1];
                if(old == ne)
                    continue;
                // beda berarti update previous jg
                if(old && tgt[a][b])
                    --cnt[a + b];
                src[a][b] = ne;
                q.push({a + 1, b});
                q.push({a, b + 1});
            }
            cout << 1 << endl;
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 6 ms 456 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 5 ms 500 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 6 ms 456 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 5 ms 500 KB Output is correct
10 Correct 12 ms 1108 KB Output is correct
11 Correct 6 ms 480 KB Output is correct
12 Correct 286 ms 14148 KB Output is correct
13 Correct 55 ms 10572 KB Output is correct
14 Correct 560 ms 18484 KB Output is correct
15 Correct 597 ms 18352 KB Output is correct
16 Correct 590 ms 19844 KB Output is correct
17 Correct 714 ms 21012 KB Output is correct
18 Correct 630 ms 20476 KB Output is correct
19 Correct 541 ms 21676 KB Output is correct
20 Correct 408 ms 21692 KB Output is correct
21 Correct 501 ms 21708 KB Output is correct