Submission #491223

#	Time	Username	Problem	Language	Result	Execution time	Memory
491223		rainboy	Paint (COI20_paint)	C11	40 / 100	172 ms	203140 KiB

paint

#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 (stderr)

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--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 31 / 31
• Subtask 4: 0 / 52