Submission #331861

#	Time	Username	Problem	Language	Result	Execution time	Memory
331861		phathnv	Furniture (JOI20_furniture)	C++11	0 / 100	3 ms	1260 KiB

furniture

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1002;
const int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[8] = {1, -1, -1, 0, 1, -1, 0, 1};

int m, n, q, a[N][N], ind[N][N], curInd;

struct DSU{
    vector <int> root, rnk;
    void init(int n){
        root.resize(n + 1);
        rnk.resize(n + 1);
        for(int i = 1; i <= n; i++){
            root[i] = i;
            rnk[i] = 0;
        }
    }
    int getRoot(int u){
        if (u == root[u])
            return u;
        return getRoot(root[u]);
    }
    void unite(int u, int v){
        u = getRoot(u);
        v = getRoot(v);
        if (rnk[u] < rnk[v])
            swap(u, v);
        root[v] = u;
        rnk[u] += (rnk[v] == rnk[u]);
    }
}dsu;

void readInput(){
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];
}

bool inside(int x, int y){
    return (0 <= x && x <= m + 1 && 0 <= y && y <= n + 1);
}

void solve(){
    for(int i = 1; i <= n; i++)
        a[0][i] = a[m + 1][i] = 1;
    for(int i = 1; i <= m; i++)
        a[i][0] = a[i][n + 1] = 1;

    for(int i = 0; i <= m + 1; i++)
        for(int j = 0; j <= n + 1; j++)
            ind[i][j] = ++curInd;
    dsu.init(curInd);
    for(int i = 2; i <= n; i++){
        dsu.unite(ind[0][i - 1], ind[0][i]);
        dsu.unite(ind[m + 1][i - 1], ind[m + 1][i]);
    }
    for(int i = 2; i <= m; i++){
        dsu.unite(ind[i - 1][0], ind[i][0]);
        dsu.unite(ind[i - 1][n + 1], ind[i][n + 1]);
    }
    dsu.unite(ind[0][n], ind[1][n + 1]);
    dsu.unite(ind[m][0], ind[m + 1][1]);

    for(int x = 1; x <= m; x++)
        for(int y = 1; y <= n; y++){
            if (!a[x][y])
                continue;
            for(int dir = 0; dir < 8; dir++)
                if (a[x + dx[dir]][y + dy[dir]])
                    dsu.unite(ind[x][y], ind[x + dx[dir]][y + dy[dir]]);
        }

    cin >> q;
    while (q--){
        int x, y;
        cin >> x >> y;
        set <int> s;
        for(int dir = 0; dir < 8; dir++)
            if (a[x + dx[dir]][y + dy[dir]])
                s.insert(dsu.getRoot(ind[x + dx[dir]][y + dy[dir]]));
        if (s.find(dsu.getRoot(ind[1][0])) != s.end() && s.find(dsu.getRoot(ind[0][1])) != s.end()) {
            cout << 0 << '\n';
        } else {
            cout << 1 << '\n';
            a[x][y] = 1;
            for(int dir = 0; dir < 8; dir++)
                if (a[x + dx[dir]][y + dy[dir]])
                    dsu.unite(ind[x][y], ind[x + dx[dir]][y + dy[dir]]);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    readInput();
    solve();
    return 0;
}

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