oj.uz

Submission #1033505

# Submission time Handle Problem Language Result Execution time Memory
1033505 2024-07-25T00:18:01 Z vjudge1 Furniture (JOI20_furniture) C++17
0 / 100
 5000 ms 275828 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
bitset<1010> reach[1010], open[1010];
int n,m;
void redo(){    
    reach[0][1]=1;
    for(int i=1;i<=m;i++) {
        reach[i]=reach[i-1]&open[i];
        for(int j=2;j<=n;j++)
            if(open[i][j]&&reach[i][j-1])
                reach[i][j]=1;
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int q;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int x;
            cin>>x;
            open[j][i]=!x;
        }
    redo();
    cin>>q;
    for(int i=1;i<=q;i++) {
        int X,Y;
        cin>>Y>>X;
        queue<pair<int,int>>q;
        q.push({X,Y});
        reach[X][Y]=0;
        while(q.size()){
            auto[a,b]=q.front();
            q.pop();
            if(!reach[a+1][b-1]&&a<m)
                q.push({a+1,b}),reach[a+1][b]=0;
            if(!reach[a-1][b+1]&&b<n)
                q.push({a,b+1}),reach[a][b+1]=0;
        }
        if(reach[m][n]){
            cout<<"1\n";
            open[X][Y]=0;
        } else redo(),
            cout<<"0\n";
    }
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5043 ms 275828 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 5043 ms 275828 KB Time limit exceeded
2 Halted 0 ms 0 KB -