Submission #1273005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273005		Persia	Paint (COI20_paint)	C++20	100 / 100	272 ms	44380 KiB

paint

#include <bits/stdc++.h>
using namespace std;
#define bit(i, x) (x >> i & 1)
#define ll long long
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define rep2(i, l, r) for(int i = l; i >= r; i--)
#define SZ(x) (x).size()
const int N = 2e5 + 5;
const int mod1 = 998244353;
const int mod2 = 1e9 + 7;
const int base = 31;
mt19937 rng(time(0));
ll rnd(ll l, ll r) {
        return rng() % (r - l + 1) + l;
}

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int K;

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

int par[N], col[N];
vector<int> adj[N];
set<int> heavy[N];
set<pair<int, int>> light[N];
bool is_heavy[N];
vector<pair<int, int>> to_add_pairs;
vector<int> to_add;

int get(int i, int j) {
        return (i - 1) * m + j;
}

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

int root(int x) {
        return (x == par[x] ? x : par[x] = root(par[x]));
}

void join(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y) return;

        if(SZ(adj[x]) < SZ(adj[y])) swap(x, y);
        if(SZ(heavy[x]) < SZ(heavy[y])) heavy[x].swap(heavy[y]);
        if(SZ(light[x]) < SZ(light[y])) light[x].swap(light[y]);

        for(auto ii : adj[y]) {
                int i = root(ii);
                if(i == x) continue;
                if(is_heavy[i]) {
                        if(is_heavy[x]) {
                                heavy[x].insert(i);
                                heavy[i].insert(x);
                        }
                        else {
                                light[i].insert({col[x], x});
                        }
                }
                else if(is_heavy[x]) {
                        light[x].insert({col[i], i});
                }
                adj[x].push_back(i);
        }

        for(auto ii : heavy[y]) {
                int i = root(ii);
                if(i == x) continue;
                heavy[x].insert(i);
        }
        for(auto ii : light[y]) {
                int i = root(ii.second);
                if(i == x) continue;
                light[x].insert({ii.first, i});
        }

        if(!is_heavy[x] && SZ(adj[x]) > K) {
                is_heavy[x] = true;
                for(auto ii : adj[x]) {
                        int i = root(ii);
                        if(i == x) continue;
                        if(is_heavy[i]) {
                                heavy[x].insert(i);
                                heavy[i].insert(x);
                        }
                        light[x].insert({col[i], i});
                }
        }

        adj[y].clear();
        heavy[y].clear();
        light[y].clear();
        par[y] = x;
}

signed main(int argc, char* argv[]) {
        ios_base::sync_with_stdio(0);
        cin.tie(0); cout.tie(0);

        cin >> n >> m;
        K = sqrt(n * m);

        a.assign(n * m + 3, 0);
        rep(i, 1, n) rep(j, 1, m) cin >> a[get(i, j)];

        rep(i, 1, n) rep(j, 1, m) {
                int r = get(i, j);
                par[r] = r;
                col[r] = a[r];
                rep(k, 0, 3) {
                        int x = i + dx[k];
                        int y = j + dy[k];
                        int t = get(x, y);
                        if(!valid(x, y)) continue;
                        if(a[r] == a[t]) to_add_pairs.push_back({r, t});
                        else adj[r].push_back(t);
                }
        }
        
        for(auto [x, y] : to_add_pairs) join(x, y);
        to_add_pairs.clear();

        cin >> q;
        
        while(q--) {
                int u, v, c; cin >> u >> v >> c;
                int r = root(get(u, v));
                if(col[r] == c) continue;
                col[r] = c;
                if(is_heavy[r]) {
                        for(auto ii : heavy[r]) {
                                int i = root(ii);
                                if(i == r) continue;
                                if(col[r] == col[i]) to_add.push_back(i);
                        }
                        while(true) {
                                auto it = light[r].lower_bound({col[r], -1});
                                if(it == light[r].end()) break;
                                if(it->first > col[r]) break;
                                int t = root(it->second);
                                if(col[t] == col[r]) to_add.push_back(t);
                                light[r].erase(it);
                        }
                }
                else {
                        for(auto ii : adj[r]) {
                                int i = root(ii);
                                if(i == r) continue;
                                if(col[r] == col[i]) to_add.push_back(i);
                                if(is_heavy[i]) light[i].insert({col[r], r});
                        }
                }
                for(auto i : to_add) join(r, i);
                to_add.clear();
        }
        
        rep(i, 1, n) {
                rep(j, 1, m) {
                        cout << col[root(get(i, j))] << " ";
                }
                cout << "\n";
        }

        return 0 ^ 0;
}

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