| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 388292 |
2021-04-10T19:38:00 Z |
PurpleCrayon |
Paint (COI20_paint) |
C++17 |
|
254 ms |
240932 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+10, B = 2;
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
if (to_small[find_set(nc)].find(get_col(o)) == to_small[find_set(nc)].end()) {
to_small[find_set(nc)][get_col(o)] = new hash_set<int>();
assert(false);
}
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) {
if (to_small[a].find(it.first) == to_small[a].end())
to_small[a][it.first] = new hash_set<int>();
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
if (to_small[find_set(nc)].find(get_col(o)) == to_small[find_set(nc)].end())
to_small[find_set(nc)][get_col(o)] = new hash_set<int>();
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) {
//cerr << "SMALL\n";
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) {
clear_small(v, find_set(v)), tt++;
bld_adj(v, find_set(v)), tt++;
}
} else {
//cerr << "BIG\n";
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)]) {
assert(get_col(nc) == 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(){
#ifndef LOCAL
ios::sync_with_stdio(false); cin.tie(0);
#endif
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
175 ms |
199112 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
189 ms |
204288 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
199 ms |
206780 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
254 ms |
240932 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
