| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 491223 |
2021-11-30T21:13:09 Z |
rainboy |
Paint (COI20_paint) |
C |
|
172 ms |
203140 KB |
#include <stdio.h>
#include <string.h>
#define NM 200000
#define S 2000
#define C 100
#define A 100000
int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };
int ds[NM], sz[NM], aa[NM], hh[NM], tt[NM], time;
int qu[NM * 4], n, m, cnt;
int ii[C], pp[C][NM], qq[C][NM], head[C][A], c;
void add(int h, int ij) {
if (qq[h][ij] == -2) {
int a = aa[ij];
pp[h][ij] = -1, qq[h][ij] = head[h][a];
if (head[h][a] != -1)
pp[h][head[h][a]] = ij;
head[h][a] = ij;
}
}
void remove_(int h, int ij) {
if (qq[h][ij] >= -1) {
int a = aa[ij], p = pp[h][ij], q = qq[h][ij];
if (p == -1)
head[h][a] = q;
else
qq[h][p] = q;
if (q != -1)
pp[h][q] = p;
pp[h][ij] = qq[h][ij] = -2;
}
}
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
void dfs1(int i, int j, int i_, int j_, int a) {
int g;
if (i < 0 || i >= n || j < 0 || j >= m || tt[i * m + j] == time)
return;
tt[i * m + j] = time;
if (find(i * m + j) != find(i_ * m + j_)) {
if (aa[find(i * m + j)] == a)
qu[cnt++] = i * m + j;
return;
}
for (g = 0; g < 4; g++)
dfs1(i + di[g], j + dj[g], i_, j_, a);
}
void dfs2(int i, int j, int r, int h) {
int g, ij;
if (i < 0 || i >= n || j < 0 || j >= m || tt[i * m + j] == time)
return;
tt[i * m + j] = time;
ij = find(i * m + j);
if (ij != r) {
if (qq[h][ij] == -3)
qq[h][ij] = -2, add(h, ij);
return;
}
for (g = 0; g < 4; g++)
dfs2(i + di[g], j + dj[g], r, h);
}
int join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return 0;
if (sz[i] + sz[j] > S) {
if (hh[i] == -1 && hh[j] == -1) {
ii[hh[i] = hh[j] = c++] = i;
time++, dfs2(i / m, i % m, find(i), hh[i]);
time++, dfs2(j / m, j % m, find(j), hh[j]);
}
else if (hh[i] == -1 && hh[j] != -1) {
hh[i] = hh[j];
time++, dfs2(i / m, i % m, find(i), hh[i]);
}
else if (hh[i] != -1 && hh[j] == -1) {
hh[j] = hh[i];
time++, dfs2(j / m, j % m, find(j), hh[j]);
}
}
if (ds[i] > ds[j])
ds[i] = j, sz[j] += sz[i];
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i, sz[i] += sz[j];
}
return 1;
}
void flush() {
while (1) {
int h, upd;
upd = 0;
for (h = 0; h < c; h++) {
int ij = find(ii[h]), a = aa[ij];
while (head[h][a] != -1) {
if (join(ij, head[h][a])) {
upd = 1;
goto out;
}
remove_(h, head[h][a]);
}
}
out:
if (!upd)
break;
}
}
int main() {
int q, h, i, j, ij;
scanf("%d%d", &n, &m);
for (h = 0; h < C; h++) {
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
pp[h][i * m + j] = qq[h][i * m + j] = -3;
memset(head[h], -1, A * sizeof *head[h]);
}
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
scanf("%d", &aa[i * m + j]);
for (ij = 0; ij < n * m; ij++)
ds[ij] = -1, sz[ij] = 1, hh[ij] = -1;
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));
}
flush();
scanf("%d", &q);
while (q--) {
int a;
scanf("%d%d%d", &i, &j, &a), i--, j--;
ij = find(i * m + j);
if (aa[ij] == a)
continue;
for (h = 0; h < c; h++)
remove_(h, ij);
if (sz[ij] <= S) {
time++, cnt = 0, dfs1(i, j, i, j, a);
aa[ij] = a;
while (cnt--)
join(ij, qu[cnt]);
} else
aa[ij] = a;
for (h = 0; h < c; h++)
add(h, ij);
flush();
}
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 'main':
paint.c:132:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
paint.c:141:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
141 | scanf("%d", &aa[i * m + j]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.c:152:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
paint.c:156:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
156 | scanf("%d%d%d", &i, &j, &a), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
41192 KB |
Output is correct |
| 2 |
Correct |
16 ms |
41712 KB |
Output is correct |
| 3 |
Correct |
22 ms |
48676 KB |
Output is correct |
| 4 |
Correct |
23 ms |
47080 KB |
Output is correct |
| 5 |
Incorrect |
24 ms |
48332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
81736 KB |
Output is correct |
| 2 |
Correct |
172 ms |
122076 KB |
Output is correct |
| 3 |
Correct |
154 ms |
203140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
200900 KB |
Output is correct |
| 2 |
Correct |
135 ms |
200924 KB |
Output is correct |
| 3 |
Correct |
153 ms |
200116 KB |
Output is correct |
| 4 |
Correct |
171 ms |
198348 KB |
Output is correct |
| 5 |
Correct |
170 ms |
193024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
158916 KB |
Output is correct |
| 2 |
Incorrect |
170 ms |
203000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
