| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 713694 |
2023-03-22T20:18:31 Z |
Bliznetc |
Paint (COI20_paint) |
C++17 |
|
3000 ms |
319592 KB |
#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 = 1000;
int color[N], _sz[N], par[N];
vector <set <int> > sus; ///neighbours for lil morty
vector <vector <set <int> > >gb; ///neighbours for big morty
vector <set <int> > large;///neighbours who are alreday big morties
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;
}
void try_big (int v) {
v = get_p(v);
if (_sz[v] > block) {
gb[v].resize(N);
for (auto i : sus[v]) {
gb[v][color[get_p(i)]].insert(get_p(i));
large[get_p(i)].insert(v);
}
}
}
void merge_big (int u, int v) {
if (_sz[u] > _sz[v]) {
swap(u, v);
}
if (_sz[u] <= block) {
for (auto i : sus[u]) {
gb[v][color[get_p(i)]].insert(i);
large[get_p(i)].insert(u);
}
}
else {
for (int i = 1; i < N; i++) {
for (auto e : gb[u][i]) {
gb[v][i].insert(get_p(e));
}
}
}
_union(u, v);
for (int i : large[u]) {
large[v].insert(get_p(i));
}
}
void merge_small(int u, int v) {
if (_sz[u] > _sz[v]) {
swap(u, v);
}
for (auto i : sus[u]) {
sus[v].insert(get_p(i));
}
for (int i : large[u]) {
large[v].insert(get_p(i));
}
_union(u, v);
try_big(v);
}
void _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);
}
}
void solve() {
cin >> n >> m;
int a[n + 7][m + 7];
gb.resize(n * m);
large.resize(n * m);
sus.resize(n * m);
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 i : sus[num]) {
large[i].insert(get_p(num));
gb[num][color[i]].insert(i);
}
}
}
}
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 (auto i : g) {
if (color[get_p(i)] != color[get_p(v)]) {
continue;
}
if (get_p(i) == get_p(v)) {
continue;
}
_merge(v, i);
}
}
else {
for (auto i : sus[v]) {
if (color[get_p(i)] != color[get_p(v)]) {
continue;
}
if (get_p(i) == get_p(v)) {
continue;
}
_merge(v, i);
}
}
v = get_p(v);
for (auto 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";
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
cout << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
472 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
7 ms |
3412 KB |
Output is correct |
| 4 |
Correct |
28 ms |
12648 KB |
Output is correct |
| 5 |
Correct |
88 ms |
13004 KB |
Output is correct |
| 6 |
Correct |
163 ms |
12832 KB |
Output is correct |
| 7 |
Correct |
0 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
14128 KB |
Output is correct |
| 2 |
Correct |
314 ms |
319592 KB |
Output is correct |
| 3 |
Execution timed out |
3022 ms |
55744 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3030 ms |
97820 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
372 ms |
72376 KB |
Output is correct |
| 2 |
Execution timed out |
3043 ms |
69028 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
