oj.uz

Submission #388079

# Submission time Handle Problem Language Result Execution time Memory
388079 2021-04-10T00:35:46 Z PurpleCrayon Paint (COI20_paint) C++17
0 / 100
 375 ms 205852 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5+10, B = 450;
const int hA[4]={1, 0, -1, 0}, kA[4]={0, 1, 0, -1};
#define sz(v) int(v.size())

#include <bits/extc++.h>
struct splitmix64_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
template <typename K, typename V, typename Hash = splitmix64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;
template <typename K, typename Hash = splitmix64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;

int n, m, p[MAXN], sz[MAXN], vis[MAXN], col[MAXN], tt=0;
hash_map<int, hash_set<int>*> to_small[MAXN];
hash_set<int> to_big[MAXN];

vector<vector<int>> g;

int find_set(int v){ return v==p[v]?v:p[v]=find_set(p[v]); }
int get_col(int v){ return col[find_set(v)]; }
void union_start(int a, int b) {
    if ((a=find_set(a))==(b=find_set(b))) return;
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a, sz[a] += sz[b], sz[b] = 0;
}
void bld_adj(int c, int o) {
    int i=c/m, j=c%m;
    vis[c]=tt;

    assert(get_col(o) == get_col(c));
    for (int k = 0; k < 4; k++) {
        int ni=i+hA[k], nj=j+kA[k], nc=ni*m+nj;
        if (ni < 0 || ni >= n || nj < 0 || nj >= m || vis[nc] == tt) continue;

        if (get_col(o) == get_col(nc)) {
            bld_adj(nc, o);
        } else {
            if (sz[find_set(nc)] >= B) {
                to_big[find_set(o)].insert(find_set(nc));
                to_big[find_set(nc)].insert(find_set(o));
            } else {
                if (to_small[o].find(get_col(nc)) == to_small[o].end())
                    to_small[o][get_col(nc)] = new hash_set<int>();

                to_small[o][get_col(nc)]->insert(find_set(nc));
            }
        }
    }
}
void clear_small(int c, int o) {
    int i=c/m, j=c%m;
    vis[c]=tt;
    for (int k = 0; k < 4; k++) {
        int ni=i+hA[k], nj=j+kA[k], nc=ni*m+nj;
        if (ni < 0 || ni >= n || nj < 0 || nj >= m || vis[nc] == tt) continue;

        if (get_col(o) == get_col(nc)) {
            clear_small(nc, o);
        } else {
            if (sz[find_set(nc)] >= B) {
                //fix color
                to_small[find_set(nc)][get_col(o)]->erase(find_set(o));
            } else { //nothing to change
            }
        }
    }
}
void merge_sets(int a, int b) {
    assert(get_col(a) == get_col(b));
    //small to large (to_small, to_big, sz)
    a = find_set(a), b = find_set(b);
    if (a == b) return;
    auto get_sz = [&](int c) -> int {
        return sz(to_small[c]) + sz(to_big[c]) + sz[c];
    };
    if (get_sz(a) < get_sz(b)) swap(a, b);
    for (auto it : to_small[b]) {
        for (auto& c : *it.second)
            to_small[a][it.first]->insert(c);
    }
    for (auto it : to_big[b])
        to_big[a].insert(it);

    p[b] = a, sz[a] += sz[b], sz[b] = 0;
}
void mrg_small(int c, int o) {
    int i=c/m, j=c%m;
    vis[c]=tt;

    for (int k = 0; k < 4; k++) {
        int ni=i+hA[k], nj=j+kA[k], nc=ni*m+nj;
        if (ni < 0 || ni >= n || nj < 0 || nj >= m || vis[nc] == tt) continue;

        if (get_col(o) == get_col(nc)) {
            merge_sets(c, nc);
            mrg_small(nc, o);
        } else { //nothing to merge
        }
    }
}
void add_small(int c, int o) {
    int i=c/m, j=c%m;
    vis[c]=tt;
    for (int k = 0; k < 4; k++) {
        int ni=i+hA[k], nj=j+kA[k], nc=ni*m+nj;
        if (ni < 0 || ni >= n || nj < 0 || nj >= m || vis[nc] == tt) continue;

        if (get_col(o) == get_col(nc)) {
            add_small(nc, o);
        } else {
            if (sz[find_set(nc)] >= B) {
                //fix color
                to_small[find_set(nc)][get_col(o)]->insert(o);
            } else { //nothing to change
            }
        }
    }
}
void pr() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << get_col(i*m+j) << ' ';
        }
        cout << '\n';
    }
}
void solve(){
    cin >> n >> m;
    g.assign(n, vector<int>(m, -1));
    for (auto& r : g) for (auto& c : r) cin >> c;

    iota(p, p+n*m, 0), fill(sz, sz+n*m, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < 4; k++) {
                int ni=i+hA[k], nj=j+kA[k];
                if (ni < 0 || ni >= n || nj < 0 || nj >= m || g[i][j] != g[ni][nj]) continue;
                union_start(i*m+j, ni*m+nj);
            }
        }
    }
    //if i'm big:
    //  - list of all big neighbors
    //  - map of color to list of components that are adjacent that are small

    memset(vis, -1, sizeof(vis));
    for (int i = 0; i < n*m; i++) if (p[i] == i) col[i] = g[i/m][i%m];
    for (int i = 0; i < n*m; i++) if (p[i] == i && sz[i] >= B) {
        bld_adj(i, i), tt++;
    }

    int q; cin >> q;
    while (q--) {
        int i, j, c; cin >> i >> j >> c, --i, --j;
        int v=i*m+j;
        if (sz[find_set(v)] < B) {

            clear_small(v, find_set(v)), tt++;
            col[find_set(v)] = c;
            mrg_small(v, find_set(v)), tt++;
            add_small(v, find_set(v)), tt++;

            if (sz[find_set(v)] >= B) {
                bld_adj(v, find_set(v)), tt++;
            }
        } else {
            col[find_set(v)] = c;
            vector<int> cbig = vector<int>(to_big[find_set(v)].begin(), to_big[find_set(v)].end());
            for (auto& nc : cbig) {
                if (get_col(nc) == get_col(v)) {
                    merge_sets(find_set(v), nc);
                }
            }
            if (to_small[find_set(v)].find(get_col(v)) != to_small[find_set(v)].end())
                for (auto nc : *to_small[find_set(v)][get_col(v)]) {
                    merge_sets(find_set(v), nc);
                }
            to_small[find_set(v)][get_col(v)] = new hash_set<int>();
        }

//        cerr << endl;
//        pr();
//        cerr << endl;
//        for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cerr << find_set(i*m+j) << ' '; cerr << endl; }
    }
//    cerr << endl;
    pr();
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    solve();
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 98120 KB Output is correct
2 Correct 94 ms 98196 KB Output is correct
3 Correct 96 ms 98372 KB Output is correct
4 Runtime error 185 ms 199304 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 98964 KB Output is correct
2 Runtime error 375 ms 203508 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 239 ms 205852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Runtime error 274 ms 203676 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -