Submission #788954

#	Time	Username	Problem	Language	Result	Execution time	Memory
788954		n1427	Furniture (JOI20_furniture)	C++17	0 / 100	5 ms	468 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> board;
vector<int> colHeight, rowLength;

struct DisjointSetUnion
{
    int rows{}, cols{};
    vector<vector<pair<int, int>>> parent;
    vector<vector<int>> rank;
    vector<vector<int>> colour;
    vector<vector<int>> leftmost, topmost, rightmost, bottommost;

    void init(const int& _rows, const int& _cols)
    {
        rows = _rows, cols = _cols;
        parent.clear(), parent.resize(rows + 2, vector<pair<int, int>>(cols + 2));
        rank.clear(), rank.resize(rows + 2, vector<int>(cols + 2, 1));
        colour.clear(), colour.resize(rows + 2, vector<int>(cols + 2, INT_MAX));
        leftmost.clear(), leftmost.resize(rows + 2, vector<int>(cols + 2, INT_MAX));
        topmost.clear(), topmost.resize(rows + 2, vector<int>(cols + 2, INT_MAX));
        rightmost.clear(), rightmost.resize(rows + 2, vector<int>(cols + 2, INT_MIN));
        bottommost.clear(), bottommost.resize(rows + 2, vector<int>(cols + 2, INT_MIN));

        for (int i = 1; i <= rows; i++)
            for (int j = 1; j <= cols; j++)
                leftmost[i][j] = rightmost[i][j] = j, topmost[i][j] = bottommost[i][j] = i;
    }

    pair<int, int> find(int i, int j)
    {
        if (parent[i][j].first == 0) return {i, j};
        return parent[i][j] = find(parent[i][j].first, parent[i][j].second);
    }

    int getColour(int i, int j)
    {
        return colour[find(i, j).first][find(i, j).second];
    }

    void setColour(int i, int j, int c)
    {
        colour[find(i, j).first][find(i, j).second] = min(c, colour[find(i, j).first][find(i, j).second]);
    }

    int getLeftmost(int i, int j)
    {
        return leftmost[find(i, j).first][find(i, j).second];
    }

    int getTopmost(int i, int j)
    {
        return topmost[find(i, j).first][find(i, j).second];
    }

    int getRightmost(int i, int j)
    {
        return rightmost[find(i, j).first][find(i, j).second];
    }

    int getBottommost(int i, int j)
    {
        return bottommost[find(i, j).first][find(i, j).second];
    }

    void unite(pair<int, int> u, pair<int, int> v)
    {
        u = find(u.first, u.second), v = find(v.first, v.second);
        if (u == v) return;
        if (rank[u.first][u.second] > rank[v.first][v.second]) swap(u, v);
        rank[v.first][v.second] += rank[u.first][u.second];
        parent[u.first][u.second] = v;
        colour[v.first][v.second] = min(colour[u.first][u.second], colour[v.first][v.second]);
        leftmost[v.first][v.second] = min(leftmost[u.first][u.second], leftmost[v.first][v.second]);
        topmost[v.first][v.second] = min(topmost[u.first][u.second], topmost[v.first][v.second]);
        rightmost[v.first][v.second] = max(rightmost[u.first][u.second], rightmost[v.first][v.second]);
        bottommost[v.first][v.second] = max(bottommost[u.first][u.second], bottommost[v.first][v.second]);
    }
} dsu;

int dx[] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[] = {1, 0, -1, 1, -1, 1, 0, -1};

int rows, cols, queries;

void printBoard()
{
    cout << "!  ";
    for (int j = 1; j <= cols; j++)
        cout << ' ' << colHeight[j];
    cout << endl;
    for (int i = 0; i <= rows + 1; cout << endl, i++)
    {
        if (1 <= i && i <= rows)
            cout << rowLength[i] << ' ';
        else
            cout << "  ";
        for (int j = 0; j <= cols + 1; j++)
        {
            if (dsu.getColour(i, j) == INT_MAX)
                cout << "- ";
            else
                cout << dsu.getColour(i, j) << ' ';
        }
    }
    cout << endl;
}

int main()
{
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);

    ios::sync_with_stdio(false);

    cin >> rows >> cols;
    dsu.init(rows, cols);
    board.resize(rows + 2, vector<int>(cols + 2, 1));
    for (int i = 1; i <= rows; i++)
        for (int j = 1; j <= cols; j++)
            cin >> board[i][j];

    colHeight.resize(cols + 2);
    rowLength.resize(rows + 2);

    for (int j = 1, i = 0; j <= cols + 1; j++)
    {
        dsu.setColour(i, j, 1);
        while (i < rows && board[i + 1][j] == 1)
        {
            dsu.unite({i, j}, {i + 1, j});
            i++;
        }
        colHeight[j] = i;
    }

    for (int i = 1, j = 0; i <= rows + 1; i++)
    {
        dsu.setColour(i, j, 2);
        while (j < cols && board[i][j + 1] == 1)
        {
            dsu.unite({i, j}, {i, j + 1});
            j++;
        }
        rowLength[i] = j;
    }

    for (int i = 1; i <= rows; i++)
        for (int j = 1; j <= cols; j++)
            if (j > rowLength[i] && i > colHeight[j] && board[i][j] == 1)
            {
                dsu.setColour(i, j, 3);
                for (int d = 0; d < 8; d++)
                {
                    int _x = i + dx[d], _y = j + dy[d];
                    if (dsu.getColour(_x, _y) == 3)
                        dsu.unite({i, j}, {_x, _y});
                }
            }

    cin >> queries;
    int cnt[4]{};
    for (int x, y, q = 1; q <= queries; q++)
    {
        cin >> x >> y;

        if (x <= colHeight[y] || y <= rowLength[x])
        {
            cout << "1\n";
            continue;
        }

        assert(dsu.getColour(x, y) == INT_MAX);

        cnt[1] = cnt[2] = cnt[3] = 0;
        for (int d = 0; d < 8; d++)
        {
            int _x = x + dx[d], _y = y + dy[d], c = dsu.getColour(_x, _y);
            if (c != INT_MAX) cnt[c]++;
        }

        if (!cnt[1] && !cnt[2] && !cnt[3])
        {
            dsu.setColour(x, y, 3);
            cout << "1\n";
            continue;
        }

        if (cnt[1] && !cnt[2] && !cnt[3])
        {
            for (int d = 0; d < 8; d++)
            {
                int _x = x + dx[d], _y = y + dy[d];
                if (dsu.getColour(_x, _y) == 1)
                {
                    dsu.unite({x, y}, {_x, _y});
                    break;
                }
            }
            cout << "1\n";
            continue;
        }

        if (!cnt[1] && cnt[2] && !cnt[3])
        {
            for (int d = 0; d < 8; d++)
            {
                int _x = x + dx[d], _y = y + dy[d];
                if (dsu.getColour(_x, _y) == 2)
                {
                    dsu.unite({x, y}, {_x, _y});
                    break;
                }
            }
            cout << "1\n";
            continue;
        }

        if (!cnt[1] && !cnt[2] && cnt[3])
        {
            for (int d = 0; d < 8; d++)
            {
                int _x = x + dx[d], _y = y + dy[d];
                if (dsu.getColour(_x, _y) == 3)
                {
                    dsu.unite({x, y}, {_x, _y});
                    break;
                }
            }
            cout << "1\n";
            continue;
        }

        if (cnt[1] && cnt[2])
        {
            cout << "0\n";
            continue;
        }

        if (cnt[1] && cnt[3])
        {
            for (int d = 0; d < 8; d++)
            {
                int _x = x + dx[d], _y = y + dy[d];
                if (dsu.getColour(_x, _y) == 3)
                {
                    dsu.unite({x, y}, {_x, _y});
                }
            }

            for (int d = 0; d < 8; d++)
            {
                int _x = x + dx[d], _y = y + dy[d], c = dsu.getColour(_x, _y);
                if (c != 3) continue;
                if (_x <= colHeight[_y] || _y <= rowLength[_x]) continue;
                int leftmost = dsu.getLeftmost(_x, _y);

                int i = colHeight[leftmost] + 1;
                for (; dsu.getColour(i, leftmost) != 3; i++)
                    dsu.unite({i - 1, leftmost}, {i, leftmost});

                dsu.unite({i - 1, leftmost}, {i, leftmost});
                for (; dsu.getColour(i, leftmost) == 1; i++)
                    dsu.unite({i - 1, leftmost}, {i, leftmost});
                colHeight[leftmost] = --i;

                for (int j = leftmost + 1; j <= cols; j++)
                {
                    dsu.unite({i, j - 1}, {i, j});
                    while (i < rows && dsu.getColour(i + 1, j) == 1)
                    {
                        dsu.unite({i, j}, {i + 1, j});
                        i++;
                    }
                    colHeight[j] = max(i, colHeight[j]);
                }
            }

            cout << "1\n";
            continue;
        }

        if (cnt[2] && cnt[3])
        {
            for (int d = 0; d < 8; d++)
            {
                int _x = x + dx[d], _y = y + dy[d], c = dsu.getColour(_x, _y);
                if (dsu.getColour(_x, _y) == 3)
                {
                    dsu.unite({x, y}, {_x, _y});
                }
            }

            for (int d = 0; d < 8; d++)
            {
                int _x = x + dx[d], _y = y + dy[d], c = dsu.getColour(_x, _y);
                if (c != 3) continue;
                if (_x <= colHeight[_y] || _y <= rowLength[_x]) continue;
                int topmost = dsu.getTopmost(_x, _y);

                int j = rowLength[topmost] + 1;
                for (; dsu.getColour(topmost, j) != 3; j++)
                    dsu.unite({topmost, j - 1}, {topmost, j});

                dsu.unite({topmost, j - 1}, {topmost, j});
                for (; dsu.getColour(topmost, j) == 2; j++)
                    dsu.unite({topmost, j - 1}, {topmost, j});
                rowLength[topmost] = --j;

                for (int i = topmost + 1; i <= rows; i++)
                {
                    dsu.unite({i - 1, j}, {i, j});
                    while (j < cols && dsu.getColour(i, j + 1) == 2)
                    {
                        dsu.unite({i, j}, {i, j + 1});
                        j++;
                    }
                    rowLength[i] = max(j, rowLength[i]);
                }
            }

            cout << "1\n";
            continue;
        }
    }
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:289:53: warning: unused variable 'c' [-Wunused-variable]
  289 |                 int _x = x + dx[d], _y = y + dy[d], c = dsu.getColour(_x, _y);
      |                                                     ^

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