Submission #516342

#	Time	Username	Problem	Language	Result	Execution time	Memory
516342		jk410	Furniture (JOI20_furniture)	C++17	100 / 100	382 ms	14888 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
struct pos{
    int x,y;
};
int N,M,Q;
bool A[1001][1001];
bool DP1[1001][1001],DP2[1002][1002];
int Cnt[2001];
int dx[2]={0,1},dy[2]={1,0};
void solve(int qx,int qy){
    if (DP1[qx][qy]&&DP2[qx][qy]&&Cnt[qx+qy]==1){
        cout<<"0\n";
        return;
    }
    A[qx][qy]=true;
    if (DP1[qx][qy]&&DP2[qx][qy])
        Cnt[qx+qy]--;
    DP1[qx][qy]=false;
    DP2[qx][qy]=false;
    queue<pos> q;
    q.push({qx,qy});
    while (!q.empty()){
        pos t=q.front();
        q.pop();
        for (int i=0; i<2; i++){
            int x=t.x+dx[i],y=t.y+dy[i];
            if (x>N||y>M||A[x][y]||!DP1[x][y]||DP1[x-1][y]||DP1[x][y-1])
                continue;
            if (DP1[x][y]&&DP2[x][y])
                Cnt[x+y]--;
            DP1[x][y]=false;
            q.push({x,y});
        }
    }
    q.push({qx,qy});
    while (!q.empty()){
        pos t=q.front();
        q.pop();
        for (int i=0; i<2; i++){
            int x=t.x-dx[i],y=t.y-dy[i];
            if (!x||!y||A[x][y]||!DP2[x][y]||DP2[x+1][y]||DP2[x][y+1])
                continue;
            if (DP1[x][y]&&DP2[x][y])
                Cnt[x+y]--;
            DP2[x][y]=false;
            q.push({x,y});
        }
    }
    cout<<"1\n";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M;
    for (int i=1; i<=N; i++){
        for (int j=1; j<=M; j++)
            cin>>A[i][j];
    }
    DP1[1][1]=true;
    for (int i=1; i<=N; i++){
        for (int j=1; j<=M; j++){
            if (!A[i][j]&&(DP1[i-1][j]||DP1[i][j-1]))
                DP1[i][j]=true;
        }
    }
    DP2[N][M]=true;
    for (int i=N; i; i--){
        for (int j=M; j; j--){
            if (!A[i][j]&&(DP2[i+1][j]||DP2[i][j+1]))
                DP2[i][j]=true;
        }
    }
    for (int i=1; i<=N; i++){
        for (int j=1; j<=M; j++){
            if (DP1[i][j]&&DP2[i][j])
                Cnt[i+j]++;
        }
    }
    cin>>Q;
    while (Q--){
        int x,y;
        cin>>x>>y;
        solve(x,y);
    }
    return 0;
}

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