Submission #381537

#	Time	Username	Problem	Language	Result	Execution time	Memory
381537		Vimmer	Paint (COI20_paint)	C++14	31 / 100	136 ms	19692 KiB

paint

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-Ofast")

#define N 200500
#define NN 100050
#define PB push_back
#define endl '\n'
#define pri(x) cout << x << endl
#define _ << " " <<
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define M ll(1e9 + 7)
#define F first
#define S second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

//ordered_set se;

int n, m;

vector <int> who[N];

int mk[N];

bool mkr[N];

int pr[N], clr[N], qr;

int fnd(int x) {if (pr[x] != x) pr[x] = fnd(pr[x]); return pr[x];}
int ind(int i, int j) {return i * m + j;}

void link(int x, int y)
{
    x = fnd(x); y = fnd(y);

    if (x == y) return;

    if (sz(who[y]) > sz(who[x]))
        swap(x, y);

    for (auto it : who[y])
        who[x].PB(it);

    pr[y] = x;
}

int b[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("1.in", "r", stdin);
//
//    freopen("1.out", "w", stdout);

    cin >> n >> m;

    int a[n][m];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            {cin >> a[i][j]; int id = ind(i, j); clr[id] = a[i][j]; pr[id] = id;}

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (i != 0 && a[i - 1][j] == a[i][j])
                link(ind(i - 1, j), ind(i, j));

            if (j != 0 && a[i][j - 1] == a[i][j])
                link(ind(i, j - 1), ind(i, j));
        }

    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
      {
          int idr = fnd(ind(i, j));

          for (int u = 0; u < 4; u++)
          {
              int cx = i + b[u][0];

              int cy = j + b[u][1];

              if (0 <= cx && cx < n && 0 <= cy && cy < m && a[cx][cy] != a[i][j])
                  who[idr].PB(fnd(ind(cx, cy)));
          }
      }

    for (int i = 0; i < n * m; i++)
    {
        int id = fnd(i);

        if (mk[id]) continue;

        mk[id] = 1;
    }

    int q;

    cin >> q;

    for (; q > 0; q--)
    {
        qr++;

        int x, y, c;

        cin >> x >> y >> c;

        x--; y--;

        int id = fnd(ind(x, y));

        if (clr[id] == c) continue;

        clr[id] = c;

        vector <int> nx; nx.clear();

        vector <int> lnk; lnk.clear();

        for (auto it : who[id])
        {
            it = fnd(it);

            if (mk[it] == qr) continue;

            mk[it] = qr;

            if (clr[it] == c)
                lnk.PB(it);
                    else nx.PB(it);
        }

        who[id] = nx;

        for (auto it : lnk)
            {
                link(fnd(id), fnd(it));
            }


    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cout << clr[fnd(ind(i, j))] << " ";

        cout << endl;
    }
}

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