| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 491357 |
2021-12-01T17:27:43 Z |
rainboy |
Paint (COI20_paint) |
C |
|
1632 ms |
276724 KB |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NM 200000
#define S 500
#define K 400
#define A 100000
int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };
int ii[K], head[K][A + 1], prev[K][NM], next[K][NM], k; char adj[K][NM];
int aa[NM], ds[NM], sz[NM], hh[NM], n, m, nm;
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
void add(int h, int ij) {
int a = aa[ij], q = head[h][a];
prev[h][ij] = -1, next[h][ij] = q, prev[h][q] = ij;
head[h][a] = ij;
adj[h][ij] = 1;
}
void delete(int h, int ij) {
int a = aa[ij], p = prev[h][ij], q = next[h][ij];
if (p == -1)
head[h][a] = q;
else
next[h][p] = q;
if (q != -1)
prev[h][q] = p;
adj[h][ij] = 0;
}
int tt[NM], time;
void dfs2(int i, int j, int r, int h) {
int ij, g;
if (i < 0 || i >= n || j < 0 || j >= m || tt[i * m + j] == time)
return;
tt[i * m + j] = time;
if ((ij = find(i * m + j)) != r) {
if (!adj[h][ij])
add(h, ij);
return;
}
for (g = 0; g < 4; g++)
dfs2(i + di[g], j + dj[g], r, h);
}
char adj_[NM];
void join(int i, int j) {
int h, tmp;
i = find(i);
j = find(j);
if (i == j)
return;
if (ds[i] == ds[j])
ds[i]--;
if (ds[i] > ds[j])
tmp = i, i = j, j = tmp;
for (h = 0; h < k; h++) {
if (adj[h][i])
adj_[h] = 1, delete(h, i);
if (adj[h][j])
adj_[h] = 1, delete(h, j);
}
if (sz[i] + sz[j] > S) {
int hi, hj, h, ij;
if (sz[i] <= S && sz[j] <= S) {
ii[hh[i] = k++] = i;
time++, dfs2(i / m, i % m, i, hh[i]);
time++, dfs2(j / m, j % m, j, hh[i]);
} else if (sz[i] <= S) {
hh[i] = hh[j];
time++, dfs2(i / m, i % m, i, hh[i]);
} else if (sz[j] <= S)
time++, dfs2(j / m, j % m, j, hh[i]);
else {
hi = hh[i], hj = hh[j];
for (ij = 0; ij < nm; ij++)
if (adj[hj][ij]) {
delete(hj, ij);
if (!adj[hi][ij])
add(hi, ij);
}
}
h = hh[i];
if (adj[h][i])
delete(h, i);
if (adj[h][j])
delete(h, j);
adj_[h] = 0;
}
ds[j] = i, sz[i] += sz[j];
for (h = 0; h < k; h++)
if (adj_[h])
adj_[h] = 0, add(h, i);
}
int dfs1(int i, int j, int r) {
int g, ij;
if (i < 0 || i >= n || j < 0 || j >= m || tt[i * m + j] == time)
return 0;
tt[i * m + j] = time;
if ((ij = find(i * m + j)) != r) {
if (aa[ij] == aa[r]) {
join(ij, r);
return 1;
}
return 0;
}
for (g = 0; g < 4; g++)
if (dfs1(i + di[g], j + dj[g], r))
return 1;
return 0;
}
void collapse(int ij) {
while (1) {
ij = find(ij);
if (hh[ij] == -1) {
time++;
if (!dfs1(ij / m, ij % m, ij))
break;
} else {
int h = hh[ij];
if (head[h][aa[ij]] == -1)
break;
join(ij, head[h][aa[ij]]);
}
}
}
int main() {
int q, h, i, j, ij;
scanf("%d%d", &n, &m), nm = n * m;
for (h = 0; h < K; h++)
memset(head[h], -1, (A + 1) * 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 < nm; ij++)
ds[ij] = -1, sz[ij] = 1, hh[ij] = -1;
for (ij = 0; ij < nm; ij++)
collapse(ij);
scanf("%d", &q);
while (q--) {
int a;
scanf("%d%d%d", &i, &j, &a), i--, j--;
ij = find(i * m + j);
for (h = 0; h < k; h++)
if (adj[h][ij])
adj_[h] = 1, delete(h, ij);
aa[ij] = a;
for (h = 0; h < k; h++)
if (adj_[h])
adj_[h] = 0, add(h, ij);
collapse(ij);
}
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:149:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | scanf("%d%d", &n, &m), nm = n * m;
| ^~~~~~~~~~~~~~~~~~~~~
paint.c:154:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
154 | scanf("%d", &aa[i * m + j]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.c:159:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
159 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
paint.c:163:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
163 | scanf("%d%d%d", &i, &j, &a), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
156792 KB |
Output is correct |
| 2 |
Correct |
72 ms |
156900 KB |
Output is correct |
| 3 |
Correct |
66 ms |
157056 KB |
Output is correct |
| 4 |
Correct |
83 ms |
157000 KB |
Output is correct |
| 5 |
Correct |
96 ms |
157188 KB |
Output is correct |
| 6 |
Correct |
144 ms |
157304 KB |
Output is correct |
| 7 |
Correct |
74 ms |
156744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
157816 KB |
Output is correct |
| 2 |
Correct |
258 ms |
161628 KB |
Output is correct |
| 3 |
Correct |
162 ms |
163404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
166160 KB |
Output is correct |
| 2 |
Correct |
167 ms |
165360 KB |
Output is correct |
| 3 |
Correct |
192 ms |
164056 KB |
Output is correct |
| 4 |
Correct |
332 ms |
171656 KB |
Output is correct |
| 5 |
Correct |
341 ms |
166916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
184 ms |
161728 KB |
Output is correct |
| 2 |
Correct |
188 ms |
163716 KB |
Output is correct |
| 3 |
Correct |
1632 ms |
259816 KB |
Output is correct |
| 4 |
Correct |
1157 ms |
276724 KB |
Output is correct |
| 5 |
Correct |
680 ms |
190660 KB |
Output is correct |
| 6 |
Correct |
242 ms |
204480 KB |
Output is correct |
| 7 |
Correct |
216 ms |
191672 KB |
Output is correct |
| 8 |
Correct |
201 ms |
182208 KB |
Output is correct |
| 9 |
Correct |
540 ms |
164376 KB |
Output is correct |
