Submission #491212

#	Time	Username	Problem	Language	Result	Execution time	Memory
491212		rainboy	Paint (COI20_paint)	C11	0 / 100	97 ms	10572 KiB

paint

#include <stdio.h>
#include <string.h>

#define NM	200000
#define S	456
#define C	456

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };

int rep[C], c;
int ds[NM], sz[NM], aa[NM], cc[NM], tt[NM], time; char adj[NM][C];
int qu[NM * 4], n, m, cnt;

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 b) {
	int h;

	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)] == b)
			qu[cnt++] = i * m + j;
		return;
	}
	for (h = 0; h < 4; h++)
		dfs1(i + di[h], j + dj[h], i_, j_, b);
}

void dfs2(int i, int j, int c) {
	int h;

	if (i < 0 || i >= n || j < 0 || j >= m || tt[i * m + j] == time)
		return;
	tt[i * m + j] = time;
	adj[find(i * m + j)][c] = 1;
	if (find(i * m + j) != find(rep[c]))
		return;
	for (h = 0; h < 4; h++)
		dfs2(i + di[h], j + dj[h], c);
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (sz[i] + sz[j] > S) {
		if (cc[i] == -1 && cc[j] == -1) {
			rep[cc[i] = cc[j] = c++] = i;
			time++, dfs2(i / m, i % m, cc[i]);
			time++, dfs2(j / m, j % m, cc[j]);
		}
		else if (cc[i] == -1 && cc[j] != -1) {
			cc[i] = cc[j];
			time++, dfs2(i / m, i % m, cc[i]);
		}
		else if (cc[i] != -1 && cc[j] == -1) {
			cc[j] = cc[i];
			time++, dfs2(j / m, j % m, cc[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];
	}
}

int propagate(int ij) {
	while (1) {
		int h, upd;

		ij = find(ij), upd = 0;
		for (h = 0; h < c; h++)
			if (adj[ij][h]) {
				int ij_ = find(rep[h]);

				if (ij_ != ij && aa[ij_] == aa[ij]) {
					join(ij_, ij);
					upd = 1;
					break;
				}
			}
		if (!upd)
			break;
	}
	return ij;
}

int main() {
	int q, i, j, ij;

	scanf("%d%d", &n, &m);
	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, cc[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));
		}
	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;
		ij = propagate(ij);
		if (sz[ij] <= S) {
			cnt = 0, time++, dfs1(i, j, i, j, a);
			while (cnt--)
				join(ij, qu[cnt]);
		}
		aa[ij] = a;
	}
	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:100:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
paint.c:103:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |    scanf("%d", &aa[i * m + j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.c:113:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
paint.c:117:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   scanf("%d%d%d", &i, &j, &a), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

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