Submission #1245218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245218		ducdev	Paint (COI20_paint)	C++20	17 / 100	661 ms	10348 KiB

paint

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

#define cell(x, y) (((x) - 1) * n + (y))

typedef long long ll;
typedef pair<int, int> ii;

const int MAX_N = 2e5;
const int MAX_Q = 1e5;
const int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

struct Query {
    int x, y, color;
    Query() {};
    Query(int x, int y, int color) : x(x), y(y), color(color) {};
};

struct DSU {
    vector<int> par, sz, lef, rig, color;
    int n;

    int findSet(int u) {
        return u == par[u] ? u : par[u] = findSet(par[u]);
    };

    int getColor(int u) {
        return color[findSet(u)];
    };

    void setColor(int u, int c) {
        color[findSet(u)] = c;
    };

    bool unionSet(int u, int v, int c) {
        u = findSet(u), v = findSet(v);

        if (sz[u] < sz[v]) swap(u, v);
        color[u] = c;

        if (u == v) return false;

        sz[u] += sz[v];
        par[v] = u;
        lef[u] = min(lef[u], lef[v]);
        rig[u] = max(rig[u], rig[v]);

        return true;
    };

    DSU() {};
    DSU(int n) : n(n) {
        par.resize(n + 1), sz.resize(n + 1), color.resize(n + 1);
        lef.resize(n + 1), rig.resize(n + 1);
        for (int u = 1; u <= n; u++) {
            par[u] = u;
            sz[u] = 1;
            lef[u] = u, rig[u] = u;
        };
    };
};

int m, n, q;
vector<Query> queries;
vector<vector<int>> a;

bool valid(int x, int y) {
    return (x >= 1 && x <= m && y >= 1 && y <= n);
};

namespace SUBTASK_1 {
    const int MN = 1e4;

    bool vis[MN + 5];
    vector<vector<int>> b;

    bool checkSubtask() {
        return m * n <= 1e4 && q <= 1e4;
    };

    void dfs(int x, int y, int color) {
        vis[cell(x, y)] = true;
        for (int i = 0; i < 4; i++) {
            int u = x + dx[i];
            int v = y + dy[i];
            if (valid(u, v) && !vis[cell(u, v)] && b[u][v] == b[x][y]) dfs(u, v, color);
        };
        b[x][y] = color;
    };

    void Solve() {
        b = a;
        for (const Query &q : queries) {
            int x = q.x, y = q.y, color = q.color;

            for (int i = 1; i <= m * n; i++) vis[i] = false;

            dfs(x, y, color);
        };
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                cout << b[i][j] << " ";
            };
            cout << '\n';
        };
    };
};  // namespace SUBTASK_1

namespace SUBTASK_2 {
    const int M = 1;
    const int N = MAX_N;
    const int Q = MAX_Q;
    bool checkSubtask() {
        return m <= M && n <= N && q <= Q;
    };

    void Solve() {
        DSU DSU(n);
        for (int i = 1; i <= n; i++) {
            DSU.unionSet(i, i, a[1][i]);
        };

        for (int i = 1; i < n; i++) {
            if (a[1][i] == a[1][i + 1]) {
                DSU.unionSet(i, i + 1, a[1][i]);
            };
        };

        for (const Query &q : queries) {
            int idx = q.y, color = q.color;
            DSU.unionSet(idx, idx, color);

            int root = DSU.findSet(idx);
            int l = DSU.lef[root], r = DSU.rig[root];
            int newL = (l - 1 == 0 ? idx : DSU.findSet(l - 1));
            int newR = (r + 1 > n ? idx : DSU.findSet(r + 1));

            if (DSU.color[newL] == color) {
                DSU.unionSet(newL, idx, color);
            };
            if (DSU.color[newR] == color) {
                DSU.unionSet(newR, idx, color);
            };
        };

        vector<int> &color = DSU.color;
        for (int i = 1; i <= n; i++) cout << color[DSU.findSet(i)] << ' ';
        cout << '\n';
    };
};  // namespace SUBTASK_2

void printMatrix(int m, int n, const vector<vector<int>> &a) {
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cout << a[i][j] << ' ';
        };
        cout << '\n';
    };
};

namespace SUBTASK_3 {
    const int SQRT = 448;

    DSU dsu[SQRT + 5];

    bool checkSubtask() {
        for (Query &q : queries)
            if (q.color > 1) return false;
        return true;
    };

    vector<vector<int>> rotate(int m, int n, const vector<vector<int>> &a) {
        vector<vector<int>> b(n + 2, vector<int>(m + 2, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                b[i][j] = a[j][i];
            };
        };
        return b;
    };

    void updateQuery(DSU &dsu, DSU &rowDSU, int x, int y, int color) {
        rowDSU.setColor(y, color);
        dsu.setColor(cell(x, y), color);

        int root = rowDSU.findSet(y);
        int l = rowDSU.lef[root], r = rowDSU.rig[root];
        int newL = (l - 1 == 0 ? y : rowDSU.findSet(l - 1));
        int newR = (r + 1 > n ? y : rowDSU.findSet(r + 1));

        if (rowDSU.color[newL] == color) {
            rowDSU.unionSet(newL, y, color);
            dsu.unionSet(cell(x, y), cell(x, newL), color);
        };
        if (rowDSU.color[newR] == color) {
            rowDSU.unionSet(newR, y, color);
            dsu.unionSet(cell(x, y), cell(x, newR), color);
        };
    };

    void Solve() {
        bool rot = false;
        vector<vector<int>> b = a;
        if (m > n) {
            b = rotate(m, n, a);
            swap(m, n);
            rot = true;
        };

        for (int i = 1; i <= m; i++) {
            dsu[i] = DSU(n);
        };

        DSU DSU(m * n);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                DSU.color[cell(i, j)] = b[i][j];
                dsu[i].color[j] = b[i][j];
                if (i > 1 && b[i][j] == b[i - 1][j]) DSU.unionSet(cell(i, j), cell(i - 1, j), b[i][j]);
            };
            for (int j = 1; j < n; j++) {
                if (b[i][j] == b[i][j + 1]) {
                    DSU.unionSet(cell(i, j), cell(i, j + 1), b[i][j]);
                    dsu[i].unionSet(j, j + 1, b[i][j]);
                };
            };
        };

        for (Query q : queries) {
            if (rot) swap(q.x, q.y);
            int y = q.y, color = q.color;
            int curColor = DSU.getColor(cell(q.x, q.y));

            if (color == curColor) continue;

            for (int x = q.x; x >= 1; x--) {
                if (dsu[x].getColor(y) == color) {
                    dsu[x].setColor(y, color);
                    DSU.unionSet(cell(x, y), cell(q.x, q.y), color);
                    break;
                };
                updateQuery(DSU, dsu[x], x, y, color);
            };

            for (int x = q.x + 1; x <= m; x++) {
                if (dsu[x].getColor(y) == color) {
                    dsu[x].setColor(y, color);
                    DSU.unionSet(cell(x, y), cell(q.x, q.y), color);
                    break;
                };
                updateQuery(DSU, dsu[x], x, y, color);
            };
        };

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                b[i][j] = DSU.getColor(cell(i, j));
            };
        };

        if (rot) {
            b = rotate(m, n, b);
            swap(m, n);
        };

        printMatrix(m, n, b);
    };
};  // namespace SUBTASK_3

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("PAINT.INP", "r")) {
        freopen("PAINT.INP", "r", stdin);
        freopen("PAINT.OUT", "w", stdout);
    };

    cin >> m >> n;
    a.resize(m + 2, vector<int>(n + 2, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        };
    };

    cin >> q;
    queries.resize(q);
    for (Query &q : queries) cin >> q.x >> q.y >> q.color;

    if (SUBTASK_1::checkSubtask())
        return SUBTASK_1::Solve(), 0;
    if (SUBTASK_2::checkSubtask())
        return SUBTASK_2::Solve(), 0;
    if (SUBTASK_3::checkSubtask())
        return SUBTASK_3::Solve(), 0;
};

Compilation message (stderr)

paint.cpp: In function 'int main()':
paint.cpp:277:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  277 |         freopen("PAINT.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:278:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  278 |         freopen("PAINT.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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