| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 491192 |
2021-11-30T17:29:16 Z |
rainboy |
Paint (COI20_paint) |
C |
|
538 ms |
21436 KB |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NM 200000
int aa[NM], n, m;
void dfs(int i, int j, int a, int c) {
if (i < 0 || i >= n || j < 0 || j >= m || aa[i * m + j] != a)
return;
aa[i * m + j] = c;
dfs(i - 1, j, a, c);
dfs(i + 1, j, a, c);
dfs(i, j - 1, a, c);
dfs(i, j + 1, a, c);
}
int ds[NM], ll[NM], rr[NM];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
void join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return;
if (ds[i] > ds[j])
ds[i] = j, ll[j] = ll[i];
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i, rr[i] = rr[j];
}
}
int *ej[NM], eo[NM];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
void merge(int i1, int i2) {
int o;
for (o = eo[i2]; o--; )
append(i1, ej[i2][o]);
free(ej[i2]), eo[i2] = 0;
}
void join_(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return;
if (ds[i] > ds[j]) {
ds[i] = j;
merge(j, i);
} else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
merge(i, j);
}
}
void collapse(int i) {
static int qu[NM * 4];
int o, o_;
if (eo[i] == 0)
return;
for (o = eo[i]; o--; )
qu[o] = ej[i][o];
o_ = eo[i];
free(ej[i]), eo[i] = 0;
for (o = o_; o--; )
join_(i, qu[o]);
}
int main() {
int q, i, j;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
scanf("%d", &aa[i * m + j]);
scanf("%d", &q);
if (n == 1) {
for (j = 0; j < m; j++)
ds[j] = -1, ll[j] = rr[j] = j;
for (j = 1; j < m; j++)
if (aa[j] == aa[j - 1])
join(j - 1, j);
while (q--) {
int a, l, r;
scanf("%*d%d%d", &j, &a), j--;
aa[find(j)] = a;
l = ll[find(j)], r = rr[find(j)];
if (l > 0 && aa[find(l - 1)] == a)
join(l - 1, j);
if (r + 1 < m && aa[find(r + 1)] == a)
join(j, r + 1);
}
for (j = 0; j < m; j++)
printf("%d ", aa[find(j)]);
printf("\n");
} else if (n * m <= 10000) {
while (q--) {
int c;
scanf("%d%d%d", &i, &j, &c), i--, j--;
if (aa[i * m + j] != c)
dfs(i, j, aa[i * m + j], c);
}
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++)
printf("%d ", aa[i * m + j]);
printf("\n");
}
} else {
memset(ds, -1, n * m * sizeof *ds);
for (i = 0; i < n * m; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++) {
if (i > 0 && aa[i * m + j] != aa[(i - 1) * m + j])
append(i * m + j, (i - 1) * m + j), append((i - 1) * m + j, i * m + j);
if (j > 0 && aa[i * m + j] != aa[i * m + (j - 1)])
append(i * m + j, i * m + (j - 1)), append(i * m + (j - 1), i * m + j);
}
for (i = 0; i < n; i++)
for (j = 0; j < m; j++) {
if (i > 0 && aa[i * m + j] == aa[(i - 1) * m + j])
join_(i * m + j, (i - 1) * m + j);
if (j > 0 && aa[i * m + j] == aa[i * m + (j - 1)])
join_(i * m + j, i * m + (j - 1));
}
while (q--) {
int c;
scanf("%d%d%d", &i, &j, &c), i--, j--;
i = find(i * m + j);
if (aa[i] != c) {
aa[i] = c;
collapse(i);
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++)
printf("%d ", aa[find(i * m + j)]);
printf("\n");
}
}
return 0;
}
Compilation message
paint.c: In function 'append':
paint.c:44:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
44 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
paint.c: In function 'main':
paint.c:90:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
paint.c:93:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | scanf("%d", &aa[i * m + j]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.c:94:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
paint.c:104:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%*d%d%d", &j, &a), j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~
paint.c:119:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | scanf("%d%d%d", &i, &j, &c), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.c:149:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | scanf("%d%d%d", &i, &j, &c), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
5 ms |
460 KB |
Output is correct |
| 4 |
Correct |
4 ms |
332 KB |
Output is correct |
| 5 |
Correct |
233 ms |
600 KB |
Output is correct |
| 6 |
Correct |
538 ms |
944 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
1392 KB |
Output is correct |
| 2 |
Correct |
47 ms |
2300 KB |
Output is correct |
| 3 |
Correct |
65 ms |
4860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
41 ms |
21436 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
16128 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
