Submission #1053351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053351		kachim2	Furniture (JOI20_furniture)	C++17	0 / 100	1 ms	348 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> p(n+2, vector<bool>(m+2, 0));
    vector<vector<bool>> rp(n+2, vector<bool>(m+2, 0));
    vector<vector<int>> inp(n+2, vector<int>(m+2, 0));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++ ){
        cin >> inp[i][j];
        }
    }
    rp[n][m] = 1;
    p[1][1] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++ ){
        if(inp[i][j] == 0){
            if(i!=1 || j!=1)
            p[i][j] = p[i-1][j] || p[i][j-1];

        }
        }
    }
    for(int i = n; i >0; i--){
        for(int j = m; j >0; j-- ){
        if(inp[i][j] == 0){

            if(i!=n || j!=m)
            rp[i][j] = rp[i+1][j] || rp[i][j+1];
        }
        }
    }
    int q;
    cin >> q;


    for(int _ = 0; _ < q; _++){
        int x, y;
        cin >> x >> y;
        if(p[x][y]){



            bool canwe = 0;
            for(int i = 1; i < x; i++){
                if(rp[i][y+1] && p[i][y+1])
                {
                    canwe=1;
                }
            }
            for(int i = x+1; i <= n; i++){
                if(rp[i][y-1] && p[i][y-1])
                {
                    canwe=1;
                }
            }
            if(!canwe){
                cout << "0\n";
                continue;
            }
            cout << "1\n";
            p[x][y] = 0;
            stack<pair<int, int>> pos;
            pos.push({x+1, y});
            pos.push({x, y+1});
            while(!pos.empty()){
                auto v = pos.top();
                pos.pop();
                if(p[v.first][v.second]){
                    p[v.first][v.second] = p[v.first-1][v.second] || p[v.first][v.second-1];
                    if(!p[v.first][v.second]){
                        pos.push({v.first+1, v.second});
                        pos.push({v.first, v.second+1});
                    }
                }
            }
            rp[x][y] = 0;
            stack<pair<int, int>> rpos;
            rpos.push({x-1, y});
            rpos.push({x, y-1});
            while(!pos.empty()){
                auto v = rpos.top();
                rpos.pop();
                if(rp[v.first][v.second]){
                    rp[v.first][v.second] = rp[v.first+1][v.second] || rp[v.first][v.second+1];
                    if(!rp[v.first][v.second]){
                        pos.push({v.first-1, v.second});
                        pos.push({v.first, v.second-1});
                    }
                }
            }
        }
    }

}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95