oj.uz

Submission #483288

# Submission time Handle Problem Language Result Execution time Memory
483288 2021-10-28T13:49:35 Z rainboy Selotejp (COCI20_selotejp) C
110 / 110
 4 ms 972 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	1000
#define M	10
#define N_	(N * M)

int n_, nu, nv;

int *ev[1 + N_], eo[1 + N_];

void append(int u, int v) {
	int o = eo[u]++;

	if (o >= 2 && (o & o - 1) == 0)
		ev[u] = (int *) realloc(ev[u], o * 2 * sizeof *ev[u]);
	ev[u][o] = v;
}

int vv[1 + N_], uu[1 + N_], dd[1 + N_];

int bfs() {
	static int qu[1 + N_];
	int u, head, cnt;

	for (u = 0; u <= nu; u++)
		dd[u] = nu;
	head = cnt = 0;
	for (u = 1; u <= nu; u++)
		if (vv[u] == 0)
			dd[u] = 0, qu[head + cnt++] = u;
	while (cnt) {
		int d, o;

		u = qu[cnt--, head++], d = dd[u] + 1;
		for (o = eo[u]; o--; ) {
			int v = ev[u][o], w = uu[v];

			if (dd[w] == nu) {
				dd[w] = d;
				if (w == 0)
					return 1;
				qu[head + cnt++] = w;
			}
		}
	}
	return 0;
}

int eo_[1 + N_];

int dfs(int u) {
	int d, o;

	if (u == 0)
		return 1;
	d = dd[u] + 1;
	for (o = eo_[u]; o--; ) {
		int v = ev[u][o], w = uu[v];

		if (dd[w] == d && dfs(w)) {
			vv[u] = v, uu[v] = u;
			eo_[u] = o + 1;
			return 1;
		}
	}
	dd[u] = nu, eo_[u] = 0;
	return 0;
}

int hopcroft_karp() {
	int u, cnt;

	cnt = 0;
	while (bfs()) {
		memcpy(eo_, eo, (1 + nu) * sizeof *eo);
		for (u = 1; u <= nu; u++)
			if (vv[u] == 0 && dfs(u))
				cnt++;
	}
	return cnt;
}

int main() {
	static char cc[N][M + 1];
	static int uu_[N][M], vv_[N][M];
	int n, m, i, j, u;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			uu_[i][j] = vv_[i][j] = -1;
			if (cc[i][j] == '#') {
				n_++;
				if (i > 0 && cc[i - 1][j] == '#')
					uu_[i][j] = ++nu;
				if (j > 0 && cc[i][j - 1] == '#')
					vv_[i][j] = ++nv;
			}
		}
	for (u = 1; u <= nu; u++)
		ev[u] = (int *) malloc(2 * sizeof *ev[u]);
	for (i = 1; i < n; i++)
		for (j = 1; j < m; j++) {
			if (uu_[i][j] != -1 && vv_[i][j] != -1)
				append(uu_[i][j], vv_[i][j]);
			if (uu_[i][j] != -1 && vv_[i - 1][j] != -1)
				append(uu_[i][j], vv_[i - 1][j]);
			if (uu_[i][j - 1] != -1 && vv_[i][j] != -1)
				append(uu_[i][j - 1], vv_[i][j]);
			if (uu_[i][j - 1] != -1 && vv_[i - 1][j] != -1)
				append(uu_[i][j - 1], vv_[i - 1][j]);
		}
	printf("%d\n", n_ - (nu + nv - hopcroft_karp()));
	return 0;
}

Compilation message

Main.c: In function 'append':
Main.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:90:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:92:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 416 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 416 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 0 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 4 ms 716 KB Output is correct
27 Correct 4 ms 844 KB Output is correct
28 Correct 3 ms 972 KB Output is correct