Submission #1263540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263540		ivopav	Furniture (JOI20_furniture)	C++20	5 / 100	5096 ms	41156 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    int m;
    cin >> n >> m;
    vector<vector<bool>> mat={};
    for (int i=0;i<n;i++){
        mat.push_back({});
        for (int j=0;j<m;j++){
            int unos;
            cin >> unos;
            mat[i].push_back(unos);
        }
    }
    vector<vector<bool>> dp1(n,vector<bool>(m,0));
    vector<vector<bool>> dp2(n,vector<bool>(m,0));
    dp1[0][0]=1;
    dp2[n-1][m-1]=1;
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (mat[i][j]){
                continue;
            }
            if (i>0 && dp1[i-1][j]){
                dp1[i][j]=1;
            }
            if (j>0 && dp1[i][j-1]){
                dp1[i][j]=1;
            }
            
        }
    }
    for (int i=n-1;i>-1;i--){
        for (int j=m-1;j>-1;j--){
            if (mat[i][j]){
                continue;
            }
            if (i<n-1 && dp2[i+1][j]){
                dp2[i][j]=1;
            }
            if (j<m-1 && dp2[i][j+1]){
                dp2[i][j]=1;
            }
            
        }
    }
    vector<set<pair<int,int>>> diag(n+m-1,set<pair<int,int>>{});
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (dp1[i][j] && dp2[i][j]){
                diag[i+j].insert({i,j});
            }
            else {
                mat[i][j]=1;
            }
        }
    }
    vector<vector<int>> zadbio(n,vector<int>(m,-1));
    int q;
    cin >> q;
    for (int i=0;i<q;i++){
        int y;
        int x;
        cin >> y >> x;
        y--;
        x--;
        if (mat[y][x]){
            cout << "1\n";
            continue;
        }
        if (diag[y+x].size()==1){
            cout << "0\n";
            continue;
        }
        cout << "1\n";
        diag[y+x].erase({y,x});
        mat[y][x]=1;
        queue<pair<int,int>> bfslis1={};
        bfslis1.push({y,x});
        zadbio[y][x]=i;
        while (bfslis1.size()>0){
            int y2=bfslis1.front().first;
            int x2=bfslis1.front().second;
            bfslis1.pop();
            if (y2!=n-1){
                if (x2==0){
                    if (zadbio[y2+1][x2]!=i){
                        diag[y2+x2+1].erase({y2+1,x2});
                        mat[y2+1][x2]=1;
                        zadbio[y2+1][x2]=i;
                        bfslis1.push({y2+1,x2});

                    }
                }
                else{
                    if (!diag[y2+x2].count({y2+1,x2-1})){
                        if (zadbio[y2+1][x2]!=i){
                            diag[y2+x2+1].erase({y2+1,x2});
                            mat[y2+1][x2]=1;
                            zadbio[y2+1][x2]=i;
                            bfslis1.push({y2+1,x2});
                        }
                    }

                }
            }
            if (x2!=m-1){
                if (y2==0){
                    if (zadbio[y2][x2+1]!=i){
                        diag[y2+x2+1].erase({y2,x2+1});
                        mat[y2][x2+1]=1;
                        zadbio[y2][x2+1]=i;
                        bfslis1.push({y2,x2+1});

                    }
                }
                else{
                    if (!diag[y2+x2].count({y2-1,x2+1})){
                        if (zadbio[y2][x2+1]!=i){
                            diag[y2+x2+1].erase({y2,x2+1});
                            mat[y2][x2+1]=1;
                            zadbio[y2][x2+1]=i;
                            bfslis1.push({y2,x2+1});
                        }
                    }

                }
            }
            
        }
        queue<pair<int,int>> bfslis2={};
        bfslis2.push({y,x});
        while (bfslis2.size()>0){
            int y2=bfslis2.front().first;
            int x2=bfslis2.front().second;
            bfslis2.pop();
            if (y2!=0){
                if (x2==m-1){
                    if (zadbio[y2-1][x2]!=i){
                        diag[y2+x2-1].erase({y2-1,x2});
                        mat[y2-1][x2]=1;
                        zadbio[y2-1][x2]=i;
                        bfslis2.push({y2-1,x2});

                    }
                }
                else{
                    if (!diag[y2+x2].count({y2-1,x2+1})){
                        if (zadbio[y2-1][x2]!=i){
                            diag[y2+x2-1].erase({y2-1,x2});
                            mat[y2-1][x2]=1;
                            zadbio[y2-1][x2]=i;
                            bfslis2.push({y2-1,x2});
                        }
                    }

                }
            }
            if (x2!=0){
                if (y2==n-1){
                    if (zadbio[y2][x2-1]!=i){
                        diag[y2+x2-1].erase({y2,x2-1});
                        mat[y2][x2-1]=1;
                        zadbio[y2][x2-1]=i;
                        bfslis2.push({y2,x2-1});

                    }
                }
                else{
                    if (!diag[y2+x2].count({y2+1,x2-1})){
                        if (zadbio[y2][x2-1]!=i){
                            diag[y2+x2-1].erase({y2,x2-1});
                            mat[y2][x2-1]=1;
                            zadbio[y2][x2-1]=i;
                            bfslis2.push({y2,x2-1});
                        }
                    }

                }
            }
            
        }
    }
}

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