oj.uz

Submission #516339

# Submission time Handle Problem Language Result Execution time Memory
516339 2022-01-21T06:44:14 Z jk410 Furniture (JOI20_furniture) C++17
0 / 100
 5000 ms 398272 KB 
#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-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+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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5038 ms 398272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5038 ms 398272 KB Time limit exceeded
2 Halted 0 ms 0 KB -