Submission #1191663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191663		nhq0914	Paint (COI20_paint)	C++17	31 / 100	122 ms	41348 KiB

paint

#include <bits/stdc++.h>
#define ord(i, j) ((i) * m + (j))
#define N(a) (int)a.size()
#define FO(i, a, b) for(int i = (a); i <= (b); ++i)
#define RE(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;

const int maxn = 2e5 + 1, Bound = 600;

int n, m, q, rt[maxn], a[maxn];
bool isHeavy[maxn];

vector <int> adj[maxn], toAdd;
vector <pair <int, int>> toAdd_pairs;
set <int> heavy[maxn];
set <pair <int, int>> light[maxn];

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

int get(const int &x) {return x == rt[x] ? x : rt[x] = get(rt[x]);}

void merge(int x, int y){
    if((x = get(x)) == (y = get(y))) return;

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

    for(int u: adj[y]){
        u = get(u);
        if(isHeavy[u]){
            if(isHeavy[x]) heavy[x].insert(u), heavy[u].insert(x);
            else light[u].insert({a[x], x});
        }
        else if(isHeavy[x]) light[x].insert({a[u], u});
        adj[x].push_back(u);
    }

    for(int u: heavy[y]) heavy[x].insert(get(u));
    for(pair <int, int> t: light[y]) light[x].insert(t);

    rt[y] = x;

    if(!isHeavy[x] && N(adj[x]) >= Bound){
        isHeavy[x] = true;
        for(int u: adj[x]){
            if((u = get(u)) == x) continue;
            light[x].insert({a[u], u});
            if(isHeavy[u]) heavy[x].insert(u), heavy[u].insert(x);
        }
    }
}

int main(){
    cin.tie(0);
    ios :: sync_with_stdio(0);

    cin >> n >> m;

    FO(i, 0, n - 1) FO(j, 0, m - 1) cin >> a[ord(i, j)];
    FO(i, 0, n - 1) FO(j, 0, m - 1){
        rt[ord(i, j)] = ord(i, j);
        FO(k, 0, 3){
            int x = i + dx[k], y = j + dy[k];
            if(x < 0 || y < 0 || x >= n || y >= m) continue;
            adj[ord(i, j)].push_back(ord(x, y));
            if(a[ord(i, j)] == a[ord(x, y)]) toAdd_pairs.push_back({ord(i, j), ord(x, y)});
        }
    }

    for(pair <int, int> &e: toAdd_pairs) merge(e.first, e.second);

    cin >> q;
    while(q--){
        int x, y, c; cin >> x >> y >> c;
        --x, --y;
        int root = get(ord(x, y));
        swap(a[root], c);

        toAdd.clear();
        if(isHeavy[root]){
            for(int u: heavy[root]){
                u = get(u);
                if(u != root && a[u] == a[root]) toAdd.push_back(u);
            }

            set <pair <int, int>> :: iterator it;
            while(true){
                it = light[root].lower_bound(make_pair(a[root], 0));
                if(it == light[root].end() || it -> first != a[root]) break;
                int u = get(it -> second);
                if(a[u] == a[root]) toAdd.push_back(u);
                light[root].erase(it);
            }
        }
        else{
            for(int u: adj[root]){
                u = get(u);
                if(u != root && a[u] == a[root]) toAdd.push_back(u);
                if(isHeavy[u]) light[u].insert({a[root], u});
            }
        }

        for(int &u: toAdd) merge(root, u);
    }

    FO(i, 0, n - 1){
        FO(j, 0, m - 1) cout << a[get(ord(i, j))] << ' ';
        cout << '\n';
    }

    return 0;
}

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