| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 713706 | Bliznetc | Paint (COI20_paint) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
//#pragma GCC target("avx2")
using namespace std;
#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector < vi > vvi;
const int N = 200100, block = 700;
int color[N], _sz[N], par[N];
pii step[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int n, m;
int get_num(int i, int j) {
return i * m + j;
}
int get_p(int v) {
if (par[v] == v) {
return v;
}
return par[v] = get_p(par[v]);
}
void _union (int u, int v) {
u = get_p(u);
v = get_p(v);
if (u == v) return;
if (_sz[u] > _sz[v]) {
swap(u, v);
}
par[u] = v;
_sz[v] += _sz[u];
}
void set_color (int v, int c) {
color[get_p(v)] = c;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
int a[n + 7][m + 7];
vector <set <int> > sus(n * m); ///neighbours for lil morty
vector <vector <set <int> > >gb(n * m); ///neighbours for big morty
vector <set <int> > large(n * m);///neighbours who are alreday big morties
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
int num = get_num(i, j);
_sz[num] = 1;
par[num] = num;
set_color(num, a[i][j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < 4; k++) {
int x = i + step[k].F;
int y = j + step[k].S;
if (x >= 0 && x < n && y >= 0 && y < m) {
if (a[i][j] == a[x][y]) {
_union(get_num(i, j), get_num(x, y));
}
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < 4; k++) {
int x = i + step[k].F;
int y = j + step[k].S;
if (x >= 0 && x < n && y >= 0 && y < m) {
if (a[i][j] != a[x][y]) {
sus[get_p(get_num(i, j))].insert(get_p(get_num(x, y)));
}
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int num = get_num(i, j);
if (get_p(num) == num && _sz[num] > block) {
gb[num].resize(N);
for (auto i1 : sus[num]) {
large[i1].insert(num);
gb[num][color[get_p(i1)]].insert(i1);
}
}
}
}
auto try_big = [&](int v) {
v = get_p(v);
gb[v].resize(N);
for (const auto i : sus[v]) {
gb[v][color[get_p(i)]].insert(get_p(i));
large[get_p(i)].insert(v);
}
};
auto merge_big = [&] (int u, int v) {
u = get_p(u);
v = get_p(v);
if (_sz[u] > _sz[v]) {
swap(u, v);
}
if (_sz[u] <= block) {
for (const int i : sus[u]) {
const int vv = get_p(i);
gb[v][color[get_p(vv)]].insert(vv);
large[get_p(vv)].insert(v);
}
}
else {
for (int i = 1; i < N; i++) {
for (const int e : gb[u][i]) {
gb[v][i].insert(get_p(e));
}
}
}
_union(u, v);
for (const int i : large[u]) {
large[v].insert(get_p(i));
}
};
auto merge_small = [&](int u, int v) {
u = get_p(u);
v = get_p(v);
if (_sz[u] > _sz[v]) {
swap(u, v);
}
_union(u, v);
for (const int i : sus[u]) {
sus[v].insert(get_p(i));
}
for (const int i : large[u]) {
large[v].insert(get_p(i));
}
if (_sz[v] > block) {
try_big(v);
}
};
auto _merge = [&](int u, int v) {
u = get_p(u);
v = get_p(v);
if (u == v) return;
if (max(_sz[u], _sz[v]) > block) {
merge_big(u, v);
}
else {
merge_small(u, v);
}
};
int q;
cin >> q;
for (int it = 1; it <= q; it++) {
int x, y, c;
cin >> x >> y >> c;
x--, y--;
int v = get_p(get_num(x, y));
set_color(v, c);
if (_sz[v] > block) {
auto g = gb[v][c];
gb[v][c].clear();
for (const int i : g) {
if (color[get_p(i)] != c {
continue;
}
if (get_p(i) == get_p(v)) {
continue;
}
_merge(v, i);
}
}
else {
auto c1 = sus[v];
for (const int i : c1) {
if (color[get_p(i)] != c) {
continue;
}
if (get_p(i) == get_p(v)) {
continue;
}
_merge(v, i);
}
}
v = get_p(v);
for (const int i : large[v]) {
gb[get_p(i)][color[v]].insert(v);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << color[get_p(get_num(i, j))] << " ";
}
cout << "\n";
}
}