oj.uz

Submission #473042

# Submission time Handle Problem Language Result Execution time Memory
473042 2021-09-14T20:08:39 Z rainboy Planinarenje (COCI18_planinarenje) C
160 / 160
 3 ms 716 KB 
/* http://blog.brucemerry.org.za/2018/01/coci-20172018-r5-analysis.html */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	5000

int *ev[N + 1], eo[N + 1], eo_[N + 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[N + 1], uu[N + 1], dd[N + 1];

int bfs() {
	static int qu[N];
	int u, head, cnt;

	for (u = 0; u <= n; u++)
		dd[u] = n;
	head = cnt = 0;
	for (u = 1; u <= n; u++)
		if (!vv[u])
			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] == n) {
				dd[w] = d;
				if (w == 0)
					return 1;
				qu[head + cnt++] = w;
			}
		}
	}
	return 0;
}

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] = n;
	return 0;
}

void hopcroft_karp() {
	int u;

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

int main() {
	int m, u, v;

	scanf("%d%d", &n, &m);
	for (u = 1; u <= n; u++)
		ev[u] = (int *) malloc(2 * sizeof *ev[u]);
	while (m--) {
		scanf("%d%d", &u, &v);
		append(u, v);
	}
	hopcroft_karp();
	for (u = 1; u <= n; u++)
		printf(dd[u] != n ? "Mirko\n" : "Slavko\n");
	return 0;
}

Compilation message

planinarenje.c: In function 'append':
planinarenje.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   13 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
planinarenje.c: In function 'main':
planinarenje.c:81:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
planinarenje.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d%d", &u, &v);
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #3
16.0 / 16.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

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 2 ms 588 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 2 ms 460 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 332 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 3 ms 332 KB Output is correct