oj.uz

Submission #1033507

# Submission time Handle Problem Language Result Execution time Memory
1033507 2024-07-25T00:20:08 Z vjudge1 Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 10420 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]&&!reach[a+1][b-1])
                q.push({a+1,b}),reach[a+1][b]=0;
            if(reach[a][b+1]&&!reach[a-1][b+1])
                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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 6 ms 592 KB Output is correct
7 Correct 7 ms 588 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 7 ms 348 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 6 ms 592 KB Output is correct
7 Correct 7 ms 588 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 7 ms 348 KB Output is correct
10 Correct 104 ms 964 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 366 ms 5040 KB Output is correct
13 Correct 37 ms 2384 KB Output is correct
14 Correct 4695 ms 10068 KB Output is correct
15 Correct 4647 ms 10420 KB Output is correct
16 Execution timed out 5032 ms 2732 KB Time limit exceeded
17 Halted 0 ms 0 KB -