oj.uz

답안 #1031829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1031829 2024-07-23T07:46:39 Z 변재우(#10964) Furniture (JOI20_furniture) C++17
100 / 100
 191 ms 35664 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=1010;
int N, M, Q, A[Nmax][Nmax], C[2*Nmax];
int B[Nmax][Nmax], B_[Nmax][Nmax];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=M; j++) cin>>A[i][j];
    }
    B[1][1]=true;
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) if(!A[i][j]) B[i][j]|=(B[i-1][j]|B[i][j-1]);
    B_[N][M]=true;
    for(int i=N; i>=1; i--) for(int j=M; j>=1; j--) if(!A[i][j]) B_[i][j]|=(B_[i+1][j]|B_[i][j+1]);
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) B[i][j]&=B_[i][j], C[i+j]+=B[i][j];
    cin>>Q;
    while(Q--) {
        int i, j; cin>>i>>j;
        if(!B[i][j]) cout<<"1\n";
        else {
            cout<<(C[i+j]>1)<<"\n";
            if(C[i+j]>1) {
                B[i][j]=false;
                queue<pair<int, int>> q;
                q.push({i, j});
                while(!q.empty()) {
                    int y=q.front().first, x=q.front().second; q.pop();
                    C[y+x]--;
                    if(B[y-1][x] && !B[y-1][x+1]) B[y-1][x]=false, q.push({y-1, x});
                    if(B[y][x-1] && !B[y+1][x-1]) B[y][x-1]=false, q.push({y, x-1});
                    if(B[y+1][x] && !B[y+1][x-1]) B[y+1][x]=false, q.push({y+1, x});
                    if(B[y][x+1] && !B[y-1][x+1]) B[y][x+1]=false, q.push({y, x+1});
                }
            }
            else C[i+j]--;
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1624 KB Output is correct
3 Correct 2 ms 1720 KB Output is correct
4 Correct 2 ms 1884 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 3 ms 2140 KB Output is correct
7 Correct 2 ms 1884 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 2 ms 1884 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1624 KB Output is correct
3 Correct 2 ms 1720 KB Output is correct
4 Correct 2 ms 1884 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 3 ms 2140 KB Output is correct
7 Correct 2 ms 1884 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 2 ms 1884 KB Output is correct
10 Correct 5 ms 2140 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 99 ms 28420 KB Output is correct
13 Correct 59 ms 24916 KB Output is correct
14 Correct 161 ms 32152 KB Output is correct
15 Correct 165 ms 32140 KB Output is correct
16 Correct 154 ms 33624 KB Output is correct
17 Correct 174 ms 35060 KB Output is correct
18 Correct 169 ms 34136 KB Output is correct
19 Correct 168 ms 35568 KB Output is correct
20 Correct 191 ms 35532 KB Output is correct
21 Correct 164 ms 35664 KB Output is correct