oj.uz

답안 #1052476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1052476 2024-08-10T14:57:11 Z j_vdd16 Furniture (JOI20_furniture) C++17
0 / 100
 4 ms 484 KB 
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

typedef uint64_t u64;
typedef int64_t i64;


int n, m;
struct DSU {
    vi parent;

    DSU(int n = 0) {
        parent = vi(n, -1);
    }  

    int get(int a) {
        if (parent[a] == -1) return a;

        return parent[a] = get(parent[a]);
    }

    void merge(int r1, int c1, int r2, int c2) {
        merge(r1 * (m + 2) + c1, r2 * (m + 2) + c2);
    }
    void merge(int a, int b) {
        a = get(a);
        b = get(b);

        if (a == b) return;

        parent[a] = b;
    }
};

bool isValid(int r, int c) {
    return r >= 0 && r < n + 2 && c >= 0 && c < m + 2;
}

vvi isWall;
// void dfs(int r, int c) {
//     if (!isValid(r, c) || isFurniture[r][c] || isWall[r][c] == 1) return;

//     isWall[r][c]--;

//     dfs(r + 1, c);
//     dfs(r, c + 1);
// }
// void dfs2(int r, int c) {
//     if (!isValid(r, c) || isFurniture[r][c] || isWall[r][c] == 0 || isWall[r][c] == 2) return;

//     isWall[r][c]--;

//     dfs2(r - 1, c);
//     dfs2(r, c - 1);
// }

DSU dsu;
void dfsFill(int r, int c, int pr, int pc) {
    if (!isValid(r, c) || !isWall[r - 1][c] || !isWall[r][c - 1]) return;
    if (isWall[r][c]) {
        dsu.merge(r, c, pr, pc);
        return;
    }

    isWall[r][c] = true;
    dsu.merge(r, c, pr, pc);

    dfsFill(r + 1, c, r, c);
    dfsFill(r, c + 1, r, c);
}
void dfsFill2(int r, int c, int pr, int pc) {
    if (!isValid(r, c) || !isWall[r + 1][c] || !isWall[r][c + 1]) return;
    if (isWall[r][c]) {
        dsu.merge(r, c, pr, pc);
        return;
    }

    isWall[r][c] = true;
    dsu.merge(r, c, pr, pc);

    dfsFill2(r - 1, c, r, c);
    dfsFill2(r, c - 1, r, c);
}

signed main() {
    cin >> n >> m;

    isWall = vvi(n + 2, vi(m + 2, true));
    isWall[0][0] = false;
    isWall[0][1] = false;
    isWall[1][1] = false;

    isWall[n + 1][m + 1] = false;
    isWall[n + 1][m] = false;
    isWall[n][m] = false;
    loop(i, n) {
        loop(j, m) {
            int x;
            cin >> x;

            isWall[i + 1][j + 1] = x;
        }
    }

    dsu = DSU((n + 2) * (m + 2));
    loop(i, n) {
        loop(j, m) {
            if (isWall[i + 1][j]) dfsFill(i + 1, j + 1, i + 1, j);
            if (isWall[i][j + 1]) dfsFill(i + 1, j + 1, i, j + 1);
            if (isWall[i + 2][j + 1]) dfsFill2(i + 1, j + 1, i + 2, j + 1);
            if (isWall[i + 1][j + 2]) dfsFill2(i + 1, j + 1, i + 1, j + 2);
        }
    }

    /*
2 5
0 0 0 0 0
0 0 0 0 0
2
2 4
1 2
    */
    
    loop(i, n + 2) {
        loop(j, m + 2) {
            if (!isWall[i][j]) continue;

            if (isValid(i - 1, j) && isWall[i - 1][j])
                dsu.merge(i - 1, j, i, j);
            
            if (isValid(i, j - 1) && isWall[i][j - 1])
                dsu.merge(i, j - 1, i, j);
        }
    }

    // loop(i, n + 2) {
    //     loop(j, m + 2) {
    //         cout << isWall[i][j] << "  ";
    //     }
    //     cout << endl;
    // }
    // loop(i, n + 2) {
    //     loop(j, m + 2) {
    //         cout << dsu.get(i * (m + 2) + j) / 10 << dsu.get(i * (m + 2) + j) % 10 << ' ';
    //     }
    //     cout << endl;
    // }

    int q;
    cin >> q;

    loop(i, q) {
        int x, y;
        cin >> x >> y;

        int topRight = dsu.get(m + 1);
        int bottomLeft = dsu.get((n + 1) * (m + 2));

        bool contains1 = dsu.get((x - 1) * (m + 2) + y) == topRight || dsu.get((x - 1) * (m + 2) + y + 1) == topRight || dsu.get(x * (m + 2) + y + 1) == topRight;
        bool contains2 = dsu.get((x + 1) * (m + 2) + y) == bottomLeft || dsu.get((x + 1) * (m + 2) + y - 1) == bottomLeft || dsu.get(x * (m + 2) + y - 1) == bottomLeft;

        if (isWall[x][y]) {
            cout << '1' << endl;
        }
        else if (contains1 && contains2) {
            cout << '0' << endl;
        }
        else {
            cout << '1' << endl;
            isWall[x][y] = true;

            if (isWall[x + 1][y]) dsu.merge(x + 1, y, x, y);
            if (isWall[x][y + 1]) dsu.merge(x, y + 1, x, y);
            if (isWall[x + 1][y + 1]) dsu.merge(x + 1, y + 1, x, y);
            if (isWall[x - 1][y]) dsu.merge(x - 1, y, x, y);
            if (isWall[x][y - 1]) dsu.merge(x, y - 1, x, y);
            if (isWall[x - 1][y - 1]) dsu.merge(x - 1, y - 1, x, y);

            dfsFill(x + 1, y, x, y);
            dfsFill(x, y + 1, x, y);
            dfsFill2(x - 1, y, x, y);
            dfsFill2(x, y - 1, x, y);
        }
    }
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 4 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 4 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -