Submission #1053697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053697		kachim2	Furniture (JOI20_furniture)	C++17	100 / 100	1588 ms	6740 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;
                        break;
                    }
                }
                if(!canwe)
                for(int i = x+1; i <= n; i++){
                    if(rp[i][y-1] && p[i][y-1])
                    {
                        canwe=1;
                        break;
                    }
                }
                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(!rpos.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]){
                            rpos.push({v.first-1, v.second});
                            rpos.push({v.first, v.second-1});
                        }
                    }
                }
            }else{
                cout << "1\n";
            }
        }
     
    }

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