Submission #623117

#	Time	Username	Problem	Language	Result	Execution time	Memory
623117		K4YAN	Furniture (JOI20_furniture)	C++17	100 / 100	305 ms	7652 KiB

furniture

//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 / 5
• Subtask 2: 95 / 95