oj.uz

답안 #1097241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1097241 2024-10-06T14:40:02 Z anmattroi Furniture (JOI20_furniture) C++14
0 / 100
 2 ms 1624 KB 
#include <bits/stdc++.h>

#define maxn 1005
#define fi first
#define se second

using namespace std;

typedef pair<int, int> ii;

int n, m, q;
int a[maxn][maxn];
int cnt[maxn+maxn];

int e[maxn][maxn];

int dv[] = {0, 1};
int dh[] = {1, 0};

int Dv[] = {0, 1, 0, -1};
int Dh[] = {1, 0, -1, 0};

void bfs() {
    queue<ii> q;
    q.push({1, 1});
    vector<vector<bool> > V1(n+1, vector<bool>(m+1, false)); V1[1][1] = true;
    while (!q.empty()) {
        auto [u, v] = q.front(); q.pop();
        for (int k = 0; k < 2; k++) {
            int i = u + dv[k], j = v + dh[k];
            if (a[i][j] || V1[i][j]) continue;
            V1[i][j] = true; q.push({i, j});
        }
    }
    q.push({n, m});
    vector<vector<bool> > V2(n+1, vector<bool>(m+1, false)); V2[n][m] = true;
    while (!q.empty()) {
        auto [u, v] = q.front(); q.pop();
        for (int k = 0; k < 2; k++) {
            int i = u - dv[k], j = v - dh[k];
            if (a[i][j] || V2[i][j]) continue;
            V2[i][j] = true; q.push({i, j});
        }

    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        e[i][j] = (V1[i][j]&V2[i][j]);
    }
}

bool check(int x, int y) {
    if (x == 1 && y == 1) return false;
    if (x == n && y == m) return false;
    return ((a[x-1][y] && a[x][y-1]) || (a[x+1][y] && a[x][y+1]));
}

void damnfs(int x, int y) {
    queue<ii> q;
    q.push({x, y});
    while (!q.empty()) {
        auto [u, v] = q.front(); q.pop();
        for (int k = 0; k < 4; k++) {
            int i = u + dv[k], j = v + dh[k];
            if (a[i][j]) continue;
            if (!e[i][j]) continue;
            if (check(i, j)) {
                e[i][j] = 0;
                --cnt[i+j];
                q.push({i, j});
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i <= n+1; i++) for (int j = 0; j <= m+1; j++) a[i][j] = 1;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    bfs();
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (e[i][j]) ++cnt[i+j];
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (a[x][y]) {
            cout << "0\n";
            continue;
        }
        if (!e[x][y]) {
            cout << "1\n";
            a[x][y] = 1;
            continue;
        }
        if (cnt[x+y] == 1) {
            cout << "0\n";
            continue;
        }
        cout << "1\n";
        a[x][y] = 1;
        e[x][y] = 0;
        --cnt[x+y];
        damnfs(x, y);
    }

}

Compilation message

furniture.cpp: In function 'void bfs()':
furniture.cpp:28:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |         auto [u, v] = q.front(); q.pop();
      |              ^
furniture.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         auto [u, v] = q.front(); q.pop();
      |              ^
furniture.cpp: In function 'void damnfs(int, int)':
furniture.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         auto [u, v] = q.front(); q.pop();
      |              ^

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1624 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1624 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -