| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 713688 |
2023-03-22T20:04:57 Z |
Bliznetc |
Paint (COI20_paint) |
C++17 |
|
3000 ms |
524288 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 = 400;
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 - 1) * 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(2 * n * m);
large.resize(2 * n * m);
sus.resize(2 * n * m);
for (int i = 1; i <= n; i++) {
for (int j = 1; 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 = 1; i <= n; i++) {
for (int j = 1; 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 >= 1 && y <= m) {
if (a[i][j] == a[x][y]) {
_union(get_num(i, j), get_num(x, y));
}
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; 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 >= 1 && 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 = 1; i <= n; i++) {
for (int j = 1; 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(get_p(num));
gb[num][color[i]].insert(i1);
}
}
}
}
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 = 1; i <= n; i++) {
for (int j = 1; 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 |
596 KB |
Output is correct |
| 2 |
Correct |
2 ms |
852 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4672 KB |
Output is correct |
| 4 |
Correct |
14 ms |
13652 KB |
Output is correct |
| 5 |
Incorrect |
53 ms |
14240 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
20960 KB |
Output is correct |
| 2 |
Runtime error |
303 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3086 ms |
170072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
338 ms |
118664 KB |
Output is correct |
| 2 |
Execution timed out |
3096 ms |
106136 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
