oj.uz

Submission #784607

# Submission time Handle Problem Language Result Execution time Memory
784607 2023-07-16T10:55:01 Z hanifchdn Furniture (JOI20_furniture) C++17
100 / 100
 962 ms 100132 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second

const int dx1[] = {0, 1};
const int dy1[] = {1, 0};
const int dx2[] = {0, 1, 0, -1};
const int dy2[] = {1, 0, -1, 0}; 

int n, m;
bool a[1005][1005], check[1005][1005], vis[1005][1005];
set<int> s1[1005], s2[1005];

void dfs1(int x, int y) {
    vis[x][y] = 1;
    if (a[x][y]) return;
    for (int i = 0; i < 2; i++) {
        int tx = x + dx1[i], ty = y + dy1[i];
        if (tx > n or ty > m) continue;
        if (!vis[tx][ty]) dfs1(tx, ty);
        check[x][y] |= check[tx][ty];
    }
}

void dfs2(int x, int y) {
    check[x][y] = 0;
    s1[y].erase(x), s1[y + 1].erase(x), s2[x].erase(y), s2[x + 1].erase(y);
    int tx = x - 1, ty = y - 1;
    if (tx >= 1 and check[tx][y] and !check[tx][y + 1]) dfs2(tx, y);
    if (ty >= 1 and check[x][ty] and !check[x + 1][ty]) dfs2(x, ty);
    tx = x + 1, ty = y + 1;
    if (tx <= n and check[tx][y] and !check[tx][y - 1]) dfs2(tx, y);
    if (ty <= m and check[x][ty] and !check[x - 1][ty]) dfs2(x, ty);
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    vis[n][m] = 1, check[n][m] = 1;
    dfs1(1, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (check[i][j] and check[i][j - 1]) s1[j].insert(i);
            if (check[i][j] and check[i - 1][j]) s2[i].insert(j);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        /*
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) cout << check[i][j] << " ";
            cout << "\n";
        }
        */
        int x, y;
        cin >> x >> y;
        if (!check[x][y]) cout << 1 << "\n";
        else {
            auto it1 = s1[y].upper_bound(x), it2 = s2[x].upper_bound(y);
            if (it1 == s1[y].end() and it2 == s2[x].end()) {
                cout << 0 << "\n";
                continue;
            }
            cout << 1 << "\n";
            dfs2(x, y);
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1108 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 5 ms 1108 KB Output is correct
4 Correct 6 ms 1236 KB Output is correct
5 Correct 5 ms 1364 KB Output is correct
6 Correct 6 ms 1704 KB Output is correct
7 Correct 5 ms 1748 KB Output is correct
8 Correct 5 ms 1768 KB Output is correct
9 Correct 5 ms 1716 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1108 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 5 ms 1108 KB Output is correct
4 Correct 6 ms 1236 KB Output is correct
5 Correct 5 ms 1364 KB Output is correct
6 Correct 6 ms 1704 KB Output is correct
7 Correct 5 ms 1748 KB Output is correct
8 Correct 5 ms 1768 KB Output is correct
9 Correct 5 ms 1716 KB Output is correct
10 Correct 7 ms 1108 KB Output is correct
11 Correct 5 ms 1236 KB Output is correct
12 Correct 898 ms 72280 KB Output is correct
13 Correct 330 ms 47996 KB Output is correct
14 Correct 918 ms 71264 KB Output is correct
15 Correct 962 ms 84900 KB Output is correct
16 Correct 533 ms 92076 KB Output is correct
17 Correct 589 ms 96960 KB Output is correct
18 Correct 777 ms 94532 KB Output is correct
19 Correct 575 ms 100036 KB Output is correct
20 Correct 650 ms 100096 KB Output is correct
21 Correct 578 ms 100132 KB Output is correct