oj.uz

Submission #491331

# Submission time Handle Problem Language Result Execution time Memory
491331 2021-12-01T14:25:24 Z rainboy Paint (COI20_paint) C
0 / 100
 3000 ms 44440 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NM	200000
#define S	2000
#define K	100
#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;
}

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;
}

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])
			adj[h][ij] = 1, add(h, ij);
		return;
	}
	for (g = 0; g < 4; g++)
		dfs2(i + di[g], j + dj[g], r, h);
}

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])
			delete(h, i);
		if (adj[h][j])
			delete(h, j);
	}
	if (sz[i] + sz[j] > S) {
		int hi, hj, h, ij;

		if (sz[i] <= S && sz[j] <= S) {
			hh[i] = k++;
			dfs2(i / m, i % m, i, hh[i]), dfs2(j / m, j % m, j, hh[i]);
		} else if (sz[i] <= S) {
			hh[i] = hh[j];
			dfs2(i / m, i % m, i, hh[i]);
		} else if (sz[j] <= S)
			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]) {
					adj[hj][ij] = 0, delete(hj, ij);
					if (!adj[hi][ij])
						adj[hi][ij] = 1, add(hi, ij);
				}
		}
		h = hh[i];
		if (adj[h][i])
			adj[h][i] = 0, delete(h, i);
		if (adj[h][j])
			adj[h][j] = 0, delete(h, j);
	}
	ds[j] = i, sz[i] += sz[j];
	for (h = 0; h < k; h++)
		if (adj[h][i] || adj[h][j])
			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])
				delete(h, ij);
		aa[ij] = a;
		for (h = 0; h < k; h++)
			if (adj[h][ij])
				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:143:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |  scanf("%d%d", &n, &m), nm = n * m;
      |  ^~~~~~~~~~~~~~~~~~~~~
paint.c:148:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |    scanf("%d", &aa[i * m + j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.c:153:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
paint.c:157:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |   scanf("%d%d%d", &i, &j, &a), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39372 KB Output is correct
2 Correct 19 ms 39432 KB Output is correct
3 Correct 20 ms 39684 KB Output is correct
4 Correct 27 ms 39692 KB Output is correct
5 Incorrect 70 ms 39704 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 41468 KB Output is correct
2 Execution timed out 3068 ms 42904 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 44440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 43576 KB Output isn't correct
2 Halted 0 ms 0 KB -