제출 #338893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
338893		blue	Furniture (JOI20_furniture)	C++11	0 / 100	27 ms	24172 KiB

furniture

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int H, W;
int pos_col[1002*1002];
vector<int> col_pos[1002*1002];
int col = 2;

void dsu_update(int p, int q)
{
    // cout << "dsu update " << p << ' ' << q << '\n';
    if(pos_col[p] == pos_col[q]) return;
    if(col_pos[pos_col[p]].size() < col_pos[pos_col[q]].size()) swap(p, q);
    // cout << p << ' ' << q << '\n';

    int colP = pos_col[p], colQ = pos_col[q];

    for(int r: col_pos[colQ])
    {
        // cout << "r = " << r << '\n';
        pos_col[r] = colP;
        col_pos[colP].push_back(r);
    }
    // cout << pos_col[p] << ' ' << pos_col[q] << '\n';
    col_pos[colQ].clear();
}

int update(int pos)
{
    set<int> cols;
    for(int x: {-W-2, 0, +W+2})
    {
        for(int y: {-1, 0, +1})
        {
            cols.insert(pos_col[pos + x + y]);
        }
    }
    if(cols.find(pos_col[1]) != cols.end() && cols.find(pos_col[W+2]) != cols.end()) return 0;

    col++;
    pos_col[pos] = col;
    col_pos[col].push_back(pos);

    for(int x: {-W-2, 0, +W+2})
    {
        for(int y: {-1, 0, +1})
        {
            if(pos_col[pos+x+y] == 0) continue;
            dsu_update(pos, pos+x+y);
        }
    }
    return 1;
}

int main()
{
    cin >> H >> W;

    for(int j = 1; j <= W; j++)
    {
        pos_col[j] = 1;
        col_pos[1].push_back(j);

        pos_col[(W+2)*(H+1) + j] = 2;
        col_pos[2].push_back((W+2)*(H+1) + j);
    }

    for(int i = 1; i <= H; i++)
    {
        pos_col[(W+2)*i] = 2;
        col_pos[2].push_back((W+2)*i);

        pos_col[(W+2)*i + W+1] = 1;
        col_pos[1].push_back((W+2)*i + W+1);
    }

    int f;
    for(int i = 1; i <= H; i++)
    {
        for(int j = 1; j <= W; j++)
        {
            cin >> f;
            if(f) update((W+2)*i + j);
        }
    }

    // cout << "-------------------------\n";
    // for(int i = 0; i <= H+1; i++)
    // {
    //     for(int j = 0; j <= W+1; j++)
    //     {
    //         cout << pos_col[(W+2)*i + j] << ' ';
    //     }
    //     cout << '\n';
    // }

    int Q;
    cin >> Q;

    int X, Y;
    for(int i = 1; i <= Q; i++)
    {
        cin >> X >> Y;
        cout << update((W+2)*X + Y) << '\n';

        // cout << "-------------------------\n";
        // for(int i = 0; i <= H+1; i++)
        // {
        //     for(int j = 0; j <= W+1; j++)
        //     {
        //         cout << pos_col[(W+2)*i + j] << ' ';
        //     }
        //     cout << '\n';
        // }
    }
}

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