Submission #710510

#	Time	Username	Problem	Language	Result	Execution time	Memory
710510		noedit	Paint (COI20_paint)	C++17	0 / 100	337 ms	331704 KiB

paint

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

using namespace std;
typedef long long ll;

const int B = 500;

vector<int> sz, p;

vector<int> clr;

vector<unordered_set<int> > g;
vector<vector<unordered_set<int> > > big_g;
vector<unordered_set<int> > big;

int get_par(int a)
{
    if (p[a] == a)
        return a;
    return p[a] = get_par(p[a]);
}

void mrg(int a, int b)
{
    a = get_par(a);
    b = get_par(b);
    if (a != b)
    {
        if (sz[a] < sz[b])
            swap(a, b);
        sz[a] += sz[b];
        p[b] = a;
    }
}

const int MAXC = 1e5 + 1;

void bigock(int a, int b)
{
    if (sz[a] < sz[b])
        swap(a, b);
    if (sz[b] < B)
    {
        for (auto& u : g[b])
        {
            int v = get_par(u);
            big_g[a][clr[get_par(v)]].insert(v);
            big[get_par(u)].insert(a);
        }
    }
    else
    {
        for (int c = 0; c < MAXC; c++)
        {
            for (auto& u : big_g[b][c])
            {
                big_g[a][c].insert(get_par(u));
            }
        }
    }
    mrg(a, b);
    for (auto& u : big[b])
    {
        big[a].insert(get_par(u));
    }
}

void add_bigock(int a)
{
    big_g[a].resize(MAXC + 1);
    for (auto& u : g[a])
    {
        big[get_par(u)].insert(a);
        big_g[a][clr[get_par(u)]].insert(get_par(u));
    }
}

void smallock(int a, int b)
{
    if (sz[a] < sz[b])
        swap(a, b);
    mrg(a, b);
    for (auto& u : g[b])
    {
        g[a].insert(get_par(u));
    }
    for (auto& u : big[b])
    {
        big[a].insert(get_par(u));
    }
    if (sz[a] >= B)
    {
        add_bigock(a);
    }
}

void mrge(int a, int b)
{
    a = get_par(a);
    b = get_par(b);
    if (a == b) return;
    if (max(sz[a], sz[b]) >= B)
    {
        bigock(a, b);
    }
    else
    {
        smallock(a, b);
    }
}

pair<int, int> delta[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void solve()
{
    int n, m;
    cin >> n >> m;
    g.resize(n * m);
    sz.resize(n * m, 1);
    p.resize(n * m);
    iota(p.begin(), p.end(), 0);
    clr.resize(n * m);
    vector<vector<int> > field(n, vector<int>(m));
    auto get_id = [&](int x, int y)
    {
        return x * m + y;
    };
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> field[i][j];
            clr[get_id(i, j)] = field[i][j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (auto&[dx, dy] : delta)
            {
                int nx = i + dx, ny = j + dy;
                if (nx >= 0 && nx < n && ny >= 0 && ny < m)
                {
                    if (field[i][j] == field[nx][ny])
                    {
                        mrg(get_id(i, j), get_id(nx, ny));
                    }
                }
            }
        }
    }
    big.resize(n * m);
    big_g.resize(n * m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (auto&[dx, dy] : delta)
            {
                int nx = i + dx, ny = j + dy;
                if (nx >= 0 && nx < n && ny >= 0 && ny < m)
                {
                    if (field[i][j] != field[nx][ny])
                    {
                        g[get_par(get_id(i, j))].insert({get_par(get_id(nx, ny))});
                    }
                }
            }
        }
    }
    for (int i = 0; i < n * m; i++)
    {
        if (get_par(i) == i && sz[i] >= B)
        {
            big_g[i].resize(MAXC + 1);
            for (auto& u : g[i])
            {
                big[u].insert(i);
                big_g[i][clr[u]].insert(u);
            }
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        int r, s, c;
        cin >> r >> s >> c;
        r--; s--;
        int v = get_par(get_id(r, s));
        clr[v] = c;
        if (sz[v] >= B)
        {
            auto bg = big_g[v][c];
            big_g[v][c].clear();
            for (auto& u : bg)
            {
                if (get_par(u) != get_par(v) && clr[get_par(u)] == c)
                {
                    mrge(v, u);
                }
            }
        }
        else
        {
            for (auto& u : g[v])
            {
                if (get_par(u) != get_par(v) && clr[get_par(u)] == c)
                {
                    mrge(v, u);
                }
            }
        }
        for (auto& u : big[get_par(v)])
        {
            big_g[get_par(u)][clr[get_par(v)]].insert(get_par(v));
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << clr[get_par(get_id(i, j))] << " ";
        }
        cout << '\n';
    }
    return;
}

signed main()
{
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //assert(mx <= 4);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
/*
1
1000000000000000000
*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52