Submission #1052340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052340		j_vdd16	Furniture (JOI20_furniture)	C++17	0 / 100	4 ms	348 KiB

furniture

#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) {
        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;
}

vvb isFurniture;
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);
}

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

    isFurniture = vvb(n + 2, vb(m + 2, true));
    isFurniture[0][0] = false;
    isFurniture[0][1] = false;
    isFurniture[1][1] = false;

    isFurniture[n + 1][m + 1] = false;
    isFurniture[n + 1][m] = false;
    isFurniture[n][m] = false;

    isWall = vvi(n + 2, vi(m + 2, 2));
    loop(i, n) {
        loop(j, m) {
            int x;
            cin >> x;

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

    dfs(0, 0);
    dfs2(n + 1, m + 1);
    
    DSU dsu((n + 2) * (m + 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 (contains1 && contains2 && !isWall[x][y]) {
            cout << '0' << endl;
        }
        else {
            cout << '1' << endl;
            isWall[x][y] = 1;

            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);
        }
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95