Submission #1251221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251221		thetrickster10	Paint (COI20_paint)	C++20	9 / 100	1002 ms	589824 KiB

paint

#include <vector>
#include <string>
#include <iostream>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <math.h>
#include <deque>
#include <algorithm>
#define ll long long
#define pii pair<int, int>
#define pip pair<int, pii>
using namespace std;
ll mod = 1000000007;
ll inf = 1LL << 50;
const int C = 100000;
vector<int> tree;
vector<int> ranks;
int boundCheck(int r, int c, int R, int S)
{
    return r < R && r >= 0 && c < S && c >= 0;
}
void dfs(int r, int c, const vector<int> &grid, int R, int S, vector<unordered_set<int>> &edgeSet)
{
    int index = r * S + c;
    int comp = tree[index];
    int dr[] = {1, -1, 0, 0};
    int dc[] = {0, 0, 1, -1};
    for (int i = 0; i < 4; i++)
    {
        int nr = dr[i] + r;
        int nc = dc[i] + c;
        int nIndex = nr * S + nc;
        if (boundCheck(nr, nc, R, S))
        {
            if (grid[nIndex] == grid[index] && tree[nIndex] == -1)
            {
                tree[nIndex] = comp;
                dfs(nr, nc, grid, R, S, edgeSet);
            }
            else if (tree[nIndex] != -1 && tree[nIndex] != comp)
            {
                int nComp = tree[nIndex];
                edgeSet[comp].insert(nComp);
                edgeSet[nComp].insert(comp);
            }
        }
    }
}

// finds root of tree with x in it (with memoization)
int find(int x)
{
    return x == tree[x] ? x : tree[x] = find(tree[x]);
}
// links two components together
void link(int x, int y)
{
    if (ranks[x] > ranks[y])
    {
        tree[y] = x;
    }
    else
    {
        tree[x] = y;
        if (ranks[x] == ranks[y])
        {
            ranks[y]++;
        }
    }
}

void intoHeavy(int heavyComp, int comp, vector<int> &grid, vector<unordered_set<int>> &edgeList, vector<vector<vector<int>>> &neighborColors, vector<bool> &heavyCompMap)
{

    //  tree[comp] = heavyComp;
    link(comp, heavyComp);
    int parentComp = tree[comp];
    // cout << parentComp << " merge " << heavyComp << " " << comp << '\n';
    for (int neighbor : edgeList[comp])
    {
        int ncomp = find(neighbor);
        if (ncomp == parentComp)
        {
            continue;
        }
        edgeList[heavyComp].insert(ncomp);
        neighborColors[heavyComp][grid[ncomp]].push_back(ncomp);
    }
    if (parentComp == comp)
    {
        swap(edgeList[comp], edgeList[heavyComp]);
        swap(neighborColors[comp], neighborColors[heavyComp]);
        heavyCompMap[comp] = true;
    }
}
void initNeighborColors(int heavyComp, vector<unordered_set<int>> &edgeList, vector<vector<vector<int>>> &neighborColors, vector<bool> &heavyCompMap, vector<int> &grid)
{
    neighborColors[heavyComp].resize(C);
    for (int neighborComp : edgeList[heavyComp])
    {
        // cout << "neighbor " << neighborComp << '\n';

        neighborComp = find(neighborComp);
        if (!heavyCompMap[neighborComp])
        {

            neighborColors[heavyComp][grid[neighborComp]].push_back(neighborComp);
        }
    }
}
void lightlight(int destComp, int comp, vector<int> &grid, vector<bool> &heavyCompMap, vector<int> &heavyComps, vector<unordered_set<int>> &edgeList, vector<vector<vector<int>>> &neighborColors, int threshold)
{

    if (edgeList[destComp].size() < edgeList[comp].size())
    {
        //      swap(comp, destComp);
    }

    link(comp, destComp);
    // tree[comp] = destComp;
    int parentComp = tree[comp];

    for (int neighbor : edgeList[comp])
    {
        int ncomp = find(neighbor);
        if (ncomp == parentComp || edgeList[destComp].count(ncomp))
        {
            continue;
        }
        edgeList[destComp].insert(ncomp);
    }
    if (parentComp == comp)
    {
        swap(edgeList[comp], edgeList[destComp]);

        swap(destComp, comp);
    }
    if (edgeList[destComp].size() >= threshold)
    {
        heavyCompMap[destComp] = true;
        heavyComps.push_back(destComp);
        initNeighborColors(destComp, edgeList, neighborColors, heavyCompMap, grid);
    }
}
void merge(int comp, int preComp, vector<int> &grid, vector<bool> &heavyCompMap, vector<int> &heavyComps, vector<unordered_set<int>> &edgeList,
           vector<vector<vector<int>>> &neighborColors, int threshold)
{
    if (comp == preComp)
    {
        return;
    }
    if (heavyCompMap[comp])
    {
        if (heavyCompMap[preComp])
        {
            if (edgeList[comp].size() < edgeList[preComp].size())
            {
                swap(comp, preComp);
            }
            intoHeavy(comp, preComp, grid, edgeList, neighborColors, heavyCompMap);
        }
        else
        {
            intoHeavy(comp, preComp, grid, edgeList, neighborColors, heavyCompMap);
        }
    }
    else
    {
        if (heavyCompMap[preComp])
        {
            intoHeavy(preComp, comp, grid, edgeList, neighborColors, heavyCompMap);
        }
        else
        {
            lightlight(preComp, comp, grid, heavyCompMap, heavyComps, edgeList, neighborColors, threshold);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin.exceptions(cin.failbit);
    int R, S;

    cin >> R >> S;
    int threshold = sqrt(R * S);
    tree = vector<int>(R * S, -1);
    ranks = vector<int>(R * S, 0);
    vector<vector<vector<int>>> neighborColors(R * S);
    vector<bool> heavyCompMap(R * S, false);
    vector<int> heavyComps;
    vector<unordered_set<int>> edgeList(R * S);
    vector<int> grid(R * S);
    for (int r = 0; r < R; r++)
    {
        for (int c = 0; c < S; c++)
        {
            int color;
            cin >> color;
            grid[r * S + c] = color;
        }
    }
    vector<int> compList;
    for (int r = 0; r < R; r++)
    {
        for (int c = 0; c < S; c++)
        {
            int index = r * S + c;
            if (tree[index] == -1)
            {
                tree[index] = index;
                dfs(r, c, grid, R, S, edgeList);

                compList.push_back(index);
            }
        }
    }
    //  for (auto comp : compList)
    // {
    //     cout << comp << ": ";
    //     for (auto edge : edgeList[comp])
    //     {
    //         cout << edge << ", ";
    //     }
    //     cout << "\n";
    // }
    for (int comp : compList)
    {
        if (edgeList[comp].size() >= threshold)
        {
            heavyCompMap[comp] = true;
            heavyComps.push_back(comp);
            neighborColors[comp].resize(C);
        }
    }
    for (int comp : heavyComps)
    {
        initNeighborColors(comp, edgeList, neighborColors, heavyCompMap, grid);
    }
    int q;
    cin >> q;
    ;
    for (int i = 0; i < q; i++)
    {
        int r, c, color;
        cin >> r >> c >> color;
        r--;
        c--;
        int comp = find(r * S + c);
        // cout << r << " " << c << " " << color << " query:\n";
        grid[comp] = color;
        if (heavyCompMap[comp])
        {
            // for (auto ncomp : heavyComps)
            // {

            //     ncomp = find(ncomp);
            //     if (comp != ncomp && grid[ncomp] == color && edgeList[comp].count(ncomp))
            //     {
            //         merge(comp, ncomp, grid, heavyCompMap, heavyComps, edgeList, neighborColors, threshold);
            //     }
            //     comp = find(comp);
            // }
            vector<int> toMerge = neighborColors[comp][color];

            // vector<int> toMerge(edgeList[comp].begin(), edgeList[comp].end());
            for (auto ncomp : toMerge)
            {

                // cout << comp << " " << ncomp << "\n";
                ncomp = find(ncomp);
                if (comp != ncomp && grid[ncomp] == color)
                {
                    merge(comp, ncomp, grid, heavyCompMap, heavyComps, edgeList, neighborColors, threshold);
                }
                comp = find(comp);
            }
            //   neighborColors[comp][color].clear();
        }
        else
        {
            vector<int> neighbors(edgeList[comp].begin(), edgeList[comp].end());
            for (auto ncomp : neighbors)
            {

                ncomp = find(ncomp);
                if (comp != ncomp && grid[ncomp] == color)
                {
                    merge(comp, ncomp, grid, heavyCompMap, heavyComps, edgeList, neighborColors, threshold);
                }
                comp = find(comp);
            }
            // if (!heavyCompMap[comp])
            // {

            //}
        }
        for (auto ncomp : heavyComps)
        {
            ncomp = find(ncomp);
            if (ncomp != comp && edgeList[comp].count(ncomp))
            {
                neighborColors[ncomp][color].push_back(comp);
            }
        }
    }
    for (int r = 0; r < R; r++)
    {
        for (int c = 0; c < S; c++)
        {
            cout << grid[find(r * S + c)] << " ";
        }
        cout << "\n";
    }
}

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