oj.uz

Submission #536354

# Submission time Handle Problem Language Result Execution time Memory
536354 2022-03-13T03:05:44 Z Monarchuwu Furniture (JOI20_furniture) C++17
100 / 100
 365 ms 25496 KB 
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 1111;
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
int m, n;
int c[N][N], id[N][N];

int par[N * N];
int root(int u) { return par[u] < 0 ? u : par[u] = root(par[u]); }
void Union(int u, int v) {
    if ((u = root(u)) == (v = root(v))) return;
    if (par[u] > par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;
}
void Join(int i, int j) {
    for (int k = 0, x, y; k < 4; ++k) {
        x = i + dx[k], y = j + dy[k];
        if (c[x][y]) Union(id[i][j], id[x][y]);
    }
}

queue<pii> q;
void bfs() {
    while (!q.empty()) {
        pii x = q.front(); q.pop();
        if (c[x.ff][x.ss]) continue;
        c[x.ff][x.ss] = 1;
        Join(x.ff, x.ss);

        if (c[x.ff - 1][x.ss + 1]) {
            if (!c[x.ff][x.ss + 1])
                q.emplace(x.ff, x.ss + 1);
            if (!c[x.ff - 1][x.ss])
                q.emplace(x.ff - 1, x.ss);
        }

        if (c[x.ff + 1][x.ss - 1]) {
            if (!c[x.ff][x.ss - 1])
                q.emplace(x.ff, x.ss - 1);
            if (!c[x.ff + 1][x.ss])
                q.emplace(x.ff + 1, x.ss);
        }
    }
}
void build() {
    memset(par, -1, sizeof(par));
    for (int i = 1; i <= m; ++i) {
        c[i][0] = c[i + 1][0] = c[i - 1][n + 1] = c[i][n + 1] = 1;
        Union(id[i][0], id[i + 1][0]);
        Union(id[i - 1][n + 1], id[i][n + 1]);
    }
    for (int j = 1; j <= n; ++j) {
        c[0][j] = c[0][j + 1] = c[m + 1][j - 1] = c[m + 1][j] = 1;
        Union(id[0][j], id[0][j + 1]);
        Union(id[m + 1][j - 1], id[m + 1][j]);
    }

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) {
            cin >> c[i][j];
            if (c[i][j]) q.emplace(i, j), c[i][j] = 0;
        }
    bfs();
}

bool check(int i, int j) {
    return (root(id[m + 1][0]) == root(id[i + 1][j - 1]) && root(id[0][n + 1]) == root(id[i - 1][j + 1]));
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 0; i <= m + 1; ++i)
        for (int j = 0; j <= n + 1; ++j) id[i][j] = i * (n + 2) + j;
    build();

    int qq, i, j; cin >> qq; while (qq--) {
        cin >> i >> j;
        if (!c[i][j]) {
            if (check(i, j)) cout << "0\n";
            else {
                cout << "1\n";
                q.emplace(i, j);
                bfs();
            }
        }
        else cout << "1\n";
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5716 KB Output is correct
2 Correct 4 ms 5972 KB Output is correct
3 Correct 4 ms 5972 KB Output is correct
4 Correct 5 ms 5972 KB Output is correct
5 Correct 5 ms 5972 KB Output is correct
6 Correct 6 ms 5972 KB Output is correct
7 Correct 5 ms 5972 KB Output is correct
8 Correct 5 ms 6056 KB Output is correct
9 Correct 5 ms 5972 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5716 KB Output is correct
2 Correct 4 ms 5972 KB Output is correct
3 Correct 4 ms 5972 KB Output is correct
4 Correct 5 ms 5972 KB Output is correct
5 Correct 5 ms 5972 KB Output is correct
6 Correct 6 ms 5972 KB Output is correct
7 Correct 5 ms 5972 KB Output is correct
8 Correct 5 ms 6056 KB Output is correct
9 Correct 5 ms 5972 KB Output is correct
10 Correct 11 ms 5716 KB Output is correct
11 Correct 6 ms 5588 KB Output is correct
12 Correct 216 ms 16756 KB Output is correct
13 Correct 82 ms 16156 KB Output is correct
14 Correct 365 ms 23116 KB Output is correct
15 Correct 350 ms 23008 KB Output is correct
16 Correct 300 ms 23968 KB Output is correct
17 Correct 339 ms 25020 KB Output is correct
18 Correct 347 ms 24360 KB Output is correct
19 Correct 263 ms 25420 KB Output is correct
20 Correct 267 ms 25376 KB Output is correct
21 Correct 297 ms 25496 KB Output is correct