Submission #491360

#	Time	Username	Problem	Language	Result	Execution time	Memory
491360		rainboy	Paint (COI20_paint)	C11	100 / 100	1796 ms	328036 KiB

paint

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

#define NM	200000
#define S	400
#define K	500
#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 (stderr)

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

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