oj.uz

Submission #482210

# Submission time Handle Problem Language Result Execution time Memory
482210 2021-10-23T17:12:55 Z rainboy Skandi (COCI20_skandi) C
110 / 110
 46 ms 7628 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	500
#define M	500
#define NU	(N * M)
#define NV	(N * M)

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

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 + NU], uu[1 + NV], dd[1 + NU], nu, nv;

int bfs() {
	static int qu[NU];
	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 + NU];

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

	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;
		}
	}
	eo_[u] = 0;
	return 0;
}

int hopcroft_karp() {
	int u, 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], inu[1 + NU], inv[1 + NV];
	static int uu_[N][M], vv_[N][M];
	int n, m, i, j, u, v, o;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	nu = 0;
	for (i = 1; i < n; i++)
		for (j = 1; j < m; j++)
			if (cc[i][j] == '0') {
				if (cc[i][j - 1] == '1')
					nu++;
				uu_[i][j] = nu;
			}
	nv = 0;
	for (j = 1; j < m; j++)
		for (i = 1; i < n; i++)
			if (cc[i][j] == '0') {
				if (cc[i - 1][j] == '1')
					nv++;
				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 (cc[i][j] == '0')
				append(uu_[i][j], vv_[i][j]);
	printf("%d\n", hopcroft_karp());
	for (u = 1; u <= nu; u++)
		if (dd[u] == nu)
			inu[u] = 1;
		else
			for (o = eo[u]; o--; ) {
				v = ev[u][o];
				inv[v] = 1;
			}
	for (i = 1; i < n; i++)
		for (j = 1; j < m; j++)
			if (cc[i][j] == '0' && cc[i][j - 1] == '1' && inu[uu_[i][j]])
				printf("%d %d DESNO\n", i + 1, j);
	for (j = 1; j < m; j++)
		for (i = 1; i < n; i++)
			if (cc[i][j] == '0' && cc[i - 1][j] == '1' && inv[vv_[i][j]])
				printf("%d %d DOLJE\n", i, j + 1);
	return 0;
}

Compilation message

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 0 ms 332 KB Correct.
3 Correct 0 ms 332 KB Correct.
4 Correct 0 ms 332 KB Correct.
5 Correct 1 ms 288 KB Correct.
6 Correct 0 ms 332 KB Correct.
7 Correct 1 ms 288 KB Correct.
8 Correct 1 ms 332 KB Correct.
9 Correct 0 ms 332 KB Correct.
10 Correct 0 ms 332 KB Correct.
11 Correct 0 ms 332 KB Correct.
12 Correct 0 ms 332 KB Correct.
13 Correct 0 ms 332 KB Correct.
14 Correct 1 ms 288 KB Correct.
15 Correct 1 ms 332 KB Correct.
16 Correct 0 ms 332 KB Correct.
17 Correct 0 ms 332 KB Correct.
18 Correct 1 ms 332 KB Correct.
19 Correct 0 ms 332 KB Correct.
20 Correct 0 ms 332 KB Correct.
21 Correct 0 ms 332 KB Correct.
22 Correct 1 ms 332 KB Correct.
23 Correct 1 ms 332 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1568 KB Correct.
2 Correct 1 ms 1100 KB Correct.
3 Correct 1 ms 1868 KB Correct.
4 Correct 1 ms 972 KB Correct.
5 Correct 1 ms 972 KB Correct.
6 Correct 1 ms 716 KB Correct.
7 Correct 1 ms 668 KB Correct.
8 Correct 1 ms 1100 KB Correct.
9 Correct 2 ms 2508 KB Correct.
10 Correct 2 ms 2508 KB Correct.
11 Correct 2 ms 2508 KB Correct.
12 Correct 1 ms 2636 KB Correct.
13 Correct 2 ms 2536 KB Correct.
14 Correct 2 ms 2524 KB Correct.
15 Correct 2 ms 2592 KB Correct.
16 Correct 2 ms 2508 KB Correct.
17 Correct 2 ms 2636 KB Correct.
18 Correct 2 ms 2636 KB Correct.
19 Correct 2 ms 2508 KB Correct.
20 Correct 1 ms 2636 KB Correct.
21 Correct 2 ms 2556 KB Correct.
22 Correct 1 ms 2508 KB Correct.
23 Correct 2 ms 2508 KB Correct.
24 Correct 1 ms 2508 KB Correct.
25 Correct 2 ms 2508 KB Correct.
26 Correct 2 ms 2592 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 0 ms 332 KB Correct.
3 Correct 0 ms 332 KB Correct.
4 Correct 0 ms 332 KB Correct.
5 Correct 1 ms 288 KB Correct.
6 Correct 0 ms 332 KB Correct.
7 Correct 1 ms 288 KB Correct.
8 Correct 1 ms 332 KB Correct.
9 Correct 0 ms 332 KB Correct.
10 Correct 0 ms 332 KB Correct.
11 Correct 0 ms 332 KB Correct.
12 Correct 0 ms 332 KB Correct.
13 Correct 0 ms 332 KB Correct.
14 Correct 1 ms 288 KB Correct.
15 Correct 1 ms 332 KB Correct.
16 Correct 0 ms 332 KB Correct.
17 Correct 0 ms 332 KB Correct.
18 Correct 1 ms 332 KB Correct.
19 Correct 0 ms 332 KB Correct.
20 Correct 0 ms 332 KB Correct.
21 Correct 0 ms 332 KB Correct.
22 Correct 1 ms 332 KB Correct.
23 Correct 1 ms 332 KB Correct.
24 Correct 1 ms 1568 KB Correct.
25 Correct 1 ms 1100 KB Correct.
26 Correct 1 ms 1868 KB Correct.
27 Correct 1 ms 972 KB Correct.
28 Correct 1 ms 972 KB Correct.
29 Correct 1 ms 716 KB Correct.
30 Correct 1 ms 668 KB Correct.
31 Correct 1 ms 1100 KB Correct.
32 Correct 2 ms 2508 KB Correct.
33 Correct 2 ms 2508 KB Correct.
34 Correct 2 ms 2508 KB Correct.
35 Correct 1 ms 2636 KB Correct.
36 Correct 2 ms 2536 KB Correct.
37 Correct 2 ms 2524 KB Correct.
38 Correct 2 ms 2592 KB Correct.
39 Correct 2 ms 2508 KB Correct.
40 Correct 2 ms 2636 KB Correct.
41 Correct 2 ms 2636 KB Correct.
42 Correct 2 ms 2508 KB Correct.
43 Correct 1 ms 2636 KB Correct.
44 Correct 2 ms 2556 KB Correct.
45 Correct 1 ms 2508 KB Correct.
46 Correct 2 ms 2508 KB Correct.
47 Correct 1 ms 2508 KB Correct.
48 Correct 2 ms 2508 KB Correct.
49 Correct 2 ms 2592 KB Correct.
50 Correct 21 ms 6468 KB Correct.
51 Correct 46 ms 4480 KB Correct.
52 Correct 32 ms 7072 KB Correct.
53 Correct 24 ms 6612 KB Correct.
54 Correct 27 ms 6184 KB Correct.
55 Correct 25 ms 7240 KB Correct.
56 Correct 21 ms 6984 KB Correct.
57 Correct 20 ms 6828 KB Correct.
58 Correct 43 ms 4416 KB Correct.
59 Correct 20 ms 6348 KB Correct.
60 Correct 25 ms 6852 KB Correct.
61 Correct 30 ms 6164 KB Correct.
62 Correct 23 ms 6852 KB Correct.
63 Correct 25 ms 6984 KB Correct.
64 Correct 7 ms 3788 KB Correct.
65 Correct 23 ms 6948 KB Correct.
66 Correct 29 ms 6340 KB Correct.
67 Correct 40 ms 6852 KB Correct.
68 Correct 27 ms 7408 KB Correct.
69 Correct 24 ms 6820 KB Correct.
70 Correct 24 ms 6816 KB Correct.
71 Correct 34 ms 7480 KB Correct.
72 Correct 24 ms 7288 KB Correct.
73 Correct 33 ms 7628 KB Correct.
74 Correct 34 ms 7404 KB Correct.
75 Correct 28 ms 7616 KB Correct.