oj.uz

답안 #1033509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033509 2024-07-25T00:24:14 Z vjudge1 Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 10216 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;
        if(!reach[X][Y]){
            cout<<"1\n";
            continue;
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 476 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 6 ms 568 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 7 ms 856 KB Output is correct

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 476 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 6 ms 568 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 7 ms 856 KB Output is correct
10 Correct 84 ms 936 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 279 ms 5052 KB Output is correct
13 Correct 33 ms 2388 KB Output is correct
14 Correct 3932 ms 10076 KB Output is correct
15 Correct 3861 ms 10216 KB Output is correct
16 Execution timed out 5061 ms 2732 KB Time limit exceeded
17 Halted 0 ms 0 KB -