oj.uz

Submission #623117

# Submission time Handle Problem Language Result Execution time Memory
623117 2022-08-05T08:24:05 Z K4YAN Furniture (JOI20_furniture) C++17
100 / 100
 305 ms 7652 KB 
//Be Name Khoda

#include<bits/stdc++.h>
//pragma shayad niaz she

using namespace std;

typedef long long ll;
typedef long double ld;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()

const ll mxn = 1e3 + 16;
ll n, m, t, q, w;
ll sum[2 * mxn];
bool exist[mxn][mxn], path[mxn][mxn], path2[mxn][mxn];

void DFS(int i, int j) {
    path[i][j] = 1;
    if(i > 1) {
        if(!path[i - 1][j] && !exist[i - 1][j]) {
            DFS(i - 1, j);
        }
    }
    if(j > 1) {
        if(!path[i][j - 1] && !exist[i][j - 1]) {
            DFS(i, j - 1);
        }
    }
}

void DFS2(int i, int j) {
    path2[i][j] = 1;
    if(path[i][j]) sum[i + j]++;
    if(i < n) {
        if(!path2[i + 1][j] && !exist[i + 1][j]) {
            DFS2(i + 1, j);
        }
    }
    if(j < m) {
        if(!path2[i][j + 1] && !exist[i][j + 1]) {
            DFS2(i, j + 1);
        }
    }
}


void BFS(int q, int w) {
    if(!path[q][w]) return;
    vector<pii> bfs;
    int ptr = 0, i, j;
    bfs.push_back({q, w});
    while(ptr < int(bfs.size())) {
        auto x = bfs[ptr++];
        i = x.first, j = x.second;
        if(!path[i][j]) continue;
        path[i][j] = 0;
        if(path2[i][j]) sum[i + j]--;
        if(i > 1) {
            if(path[i - 1][j] && !path[i - 1][j + 1]) {
                bfs.push_back({i - 1, j});
            }
        } if(j > 1) {
            if(path[i][j - 1] && !path[i + 1][j - 1]) {
                bfs.push_back({i, j - 1});
            }
        }
    } return;
}
void BFS2(int q, int w) {
    if(!path2[q][w]) return;
    vector<pii> bfs;
    int ptr = 0, i, j;
    bfs.push_back({q, w});
    while(ptr < int(bfs.size())) {
        auto x = bfs[ptr++];
        i = x.first, j = x.second;
        if(!path2[i][j]) continue;
        path2[i][j] = 0;
        if(path[i][j]) sum[i + j]--;
        if(i < n) {
            if(path2[i + 1][j] && !path2[i + 1][j - 1]) {
                bfs.push_back({i + 1, j});
            }
        } if(j < m) {
            if(path2[i][j + 1] && !path2[i - 1][j + 1]) {
                bfs.push_back({i, j + 1});
            }
        }
    } return;
}

void input() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> exist[i][j];
        }
    } cin >> t;

}

void solve() {

    DFS(n, m);
    DFS2(1, 1);
    for(int tt = 0; tt < t; tt++) {
        cin >> q >> w;
        if(!path[q][w] && !path2[q][w]) {
            cout << "1\n";
            continue;
        }
        if(!path[q][w] && path2[q][w]) {
            cout << "1\n";
            BFS2(q, w);
            continue;
        }
        if(path[q][w] && !path2[q][w]) {
            cout << "1\n";
            BFS(q, w);
            continue;
        }
        if(sum[q + w] == 1) {
            cout << "0\n";
            continue;
        }
        if(sum[q + w] > 1) {
            cout << "1\n";
            BFS(q, w), BFS2(q, w);
        }
    }
    return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}
/*
2 3
0 0 1
0 0 0
3
2 2
2 1
1 2
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 5 ms 668 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 596 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 5 ms 668 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 9 ms 596 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 147 ms 4504 KB Output is correct
13 Correct 61 ms 3376 KB Output is correct
14 Correct 234 ms 5240 KB Output is correct
15 Correct 228 ms 5312 KB Output is correct
16 Correct 226 ms 5316 KB Output is correct
17 Correct 290 ms 5624 KB Output is correct
18 Correct 305 ms 5352 KB Output is correct
19 Correct 229 ms 5820 KB Output is correct
20 Correct 270 ms 7652 KB Output is correct
21 Correct 272 ms 7316 KB Output is correct