Submission #488548

#	Time	Username	Problem	Language	Result	Execution time	Memory
488548		rainboy	Logičari (COCI21_logicari)	C11	110 / 110	53 ms	8136 KiB

Main

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

#define N	100000
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int *ej[N], eo[N], dd[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int dp[N][2][2];

void dfs(int i) {
	int o, c, d;

	if (dd[i] == eo[i] - 1) {
		dd[i] = -1;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (dd[j] != -1) {
				for (c = 0; c < 2; c++)
					for (d = 1; d >= 0; d--) {
						int x = INF;

						if (dp[i][0][1 - c] != INF)
							x = min(x, dp[j][c][d] + dp[i][0][1 - c]);
						if (d == 1 && dp[i][1][1 - c] != INF)
							x = min(x, dp[j][c][0] + dp[i][1][1 - c]);
						dp[j][c][d] = x;
					}
				dd[j]++, dfs(j);
				break;
			}
		}
	}
}

int main() {
	static int qu[N], dp_[2][2][2][2], dq_[2][2][2][2];
	int n, h, i, j, o, cnt, c1, d1, c2, d2, c3, d3, ans;

	scanf("%d", &n);
	if (n > N) {
		printf("%d\n", n % 4 == 0 ? n / 2 : -1);
		return 0;
	}
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	for (i = 0; i < n; i++)
		dp[i][0][0] = 0, dp[i][0][1] = INF, dp[i][1][0] = 1, dp[i][1][1] = INF;
	for (i = 0; i < n; i++)
		dfs(i);
	for (i = 0; i < n; i++)
		if (dd[i] != -1)
			break;
	cnt = 0;
	while (dd[i] != -1) {
		dd[i] = -1, qu[cnt++] = i;
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (dd[j] != -1) {
				i = j;
				break;
			}
		}
	}
	for (c1 = 0; c1 < 2; c1++)
		for (d1 = 0; d1 < 2; d1++)
			for (c2 = 0; c2 < 2; c2++)
				for (d2 = 0; d2 < 2; d2++)
					dp_[c1][d1][c2][d2] = INF;
	for (c1 = 0; c1 < 2; c1++)
		for (d1 = 0; d1 < 2; d1++)
			for (c2 = 0; c2 < 2; c2++)
				for (d2 = 0; d2 < 2; d2++) {
					if (d1 + c2 > 1 || d2 + c1 > 1)
						continue;
					dp_[c1][d1 + c2][c2][d2 + c1] = min(dp_[c1][d1 + c2][c2][d2 + c1], dp[qu[0]][c1][d1] + dp[qu[1]][c2][d2]);
				}
	for (h = 2; h < cnt; h++) {
		i = qu[h];
		for (c1 = 0; c1 < 2; c1++)
			for (d1 = 0; d1 < 2; d1++)
				for (c2 = 0; c2 < 2; c2++)
					for (d2 = 0; d2 < 2; d2++)
						dq_[c1][d1][c2][d2] = INF;
		for (c1 = 0; c1 < 2; c1++)
			for (d1 = 0; d1 < 2; d1++)
				for (c2 = 0; c2 < 2; c2++)
					for (d2 = 0; d2 < 2; d2++) {
						int x = dp_[c1][d1][c2][d2];

						if (x == INF)
							continue;
						for (c3 = 0; c3 < 2; c3++)
							for (d3 = 0; d3 < 2; d3++) {
								int y = dp[i][c3][d3];

								if (d2 + c3 != 1 || d3 + c2 > 1 || y == INF)
									continue;
								dq_[c1][d1][c3][d3 + c2] = min(dq_[c1][d1][c3][d3 + c2], x + y);
							}
					}
		for (c1 = 0; c1 < 2; c1++)
			for (d1 = 0; d1 < 2; d1++)
				for (c2 = 0; c2 < 2; c2++)
					for (d2 = 0; d2 < 2; d2++)
						dp_[c1][d1][c2][d2] = dq_[c1][d1][c2][d2];
	}
	ans = INF;
	for (c1 = 0; c1 < 2; c1++)
		for (d1 = 0; d1 < 2; d1++)
			for (c2 = 0; c2 < 2; c2++)
				for (d2 = 0; d2 < 2; d2++)
					if (d1 + c2 == 1 && d2 + c1 == 1)
						ans = min(ans, dp_[c1][d1][c2][d2]);
	if (ans == INF)
		ans = -1;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40
• Subtask 4: 50 / 50