Submission #1254878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254878		ender_shayan	Furniture (JOI20_furniture)	C++20	0 / 100	1 ms	1604 KiB

furniture

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

typedef long long   ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;


#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define S           second
#define F           first
#define pb          push_back
#define for1(n)     for(int i=1;i<=n;i++)
#define for0(n)     for(int i=0;i<n;i++)
#define endl        '\n'
#define Mp          make_pair
#define all(x)      x.begin(),x.end();

const ll mod=1e9+7;
const ll inf=1e18+10;

const int N=1e3+10,L=21;
int A[N][N],B[N],C[N],D[N],n,m,q,k,dp[N],pre[N],is[N][N],iss[N][N],num[N*2];
vector<int>g[N];

void bfs(int x,int y){
    if(is[x][y] && iss[x][y])num[x+y]--;
    A[x][y]=1;
    queue<pii>q;
    if(is[x][y]){
        is[x][y]=0;
        q.push({x,y});
        while(q.size()){
            int x=q.front().F,y=q.front().S;q.pop();
            if(is[x-1][y]==1 && is[x-1][y+1]==0){
                is[x-1][y]=0;
                if(iss[x-1][y])num[x+y-1]--;
                q.push({x-1,y});
            }
            if(is[x][y-1]==1 && is[x+1][y-1]==0){
                is[x][y-1]=0;
                if(iss[x][y-1])num[x+y-1]--;
                q.push({x,y-1});
            }
        }
    }
    if(iss[x][y]){
        iss[x][y]=0;
        q.push({x,y});
        while(q.size()){
            int x=q.front().F,y=q.front().S;q.pop();
            if(iss[x+1][y]==1 && iss[x+1][y-1]==0){
                iss[x+1][y]=0;
                if(is[x+1][y])num[x+y+1]--;
                q.push({x+1,y});
            }
            if(iss[x][y+1]==1 && is[x-1][y+1]==0){
                iss[x][y+1]=0;
                if(is[x][y+1])num[x+y+1]--;
                q.push({x,y+1});
            }
        }
    }
}
int main(){
    fast_io
    cin>>n>>m;
    for1(m+2)A[0][i]=A[n+1][i]=1;
    for1(n){
        for(int j=1;j<=m;j++){
            is[i][j]=iss[i][j]=1;
            num[i+j]++;
        }
    }
    for1(n){
        A[i][0]=A[i][m+1]=1;
        for(int j=1;j<=m;j++)
            cin>>A[i][j];
    }
    for1(n){
        for(int j=1;j<=m;j++)if(A[i][j])bfs(i,j);
    }
    cin>>q;
    while(q--){
        int x,y;cin>>x>>y;
        if((num[x+y]>1 || is[x][y]==0 || iss[x][y]==0) && A[x][y]==0){
            bfs(x,y);
            cout<<"1\n";
        }
        else cout<<"0\n";
    }

}

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