Submission #395148

#	Time	Username	Problem	Language	Result	Execution time	Memory
395148		rainboy	Geppetto (COCI15_geppetto)	C11	80 / 80	1 ms	208 KiB

geppetto

#include <stdio.h>

#define N	20
#define N_	(N / 2)

int main() {
	static int adj[N], cnt[1 << N_], adj_[1 << N_];
	int n, n1, n2, m, i, j, b, ans;

	scanf("%d%d", &n, &m), n1 = n / 2, n2 = n - n1;
	while (m--) {
		scanf("%d%d", &i, &j), i--, j--;
		adj[i] |= 1 << j, adj[j] |= 1 << i;
	}
	for (b = 0; b < 1 << n1; b++) {
		cnt[b] = 1;
		for (i = 0; i < n1; i++)
			if ((b & 1 << i) != 0 && (adj[i] & b) != 0) {
				cnt[b] = 0;
				break;
			}
	}
	for (i = 0; i < n1; i++)
		for (b = 0; b < 1 << n1; b++)
			if ((b & 1 << i) != 0)
				cnt[b] += cnt[b ^ 1 << i];
	for (i = n1; i < n; i++)
		adj_[1 << i - n1] = adj[i];
	for (i = 0; i < n2; i++)
		for (b = 0; b < 1 << n2; b++)
			if ((b & 1 << i) != 0)
				adj_[b] |= adj_[b ^ 1 << i];
	ans = 0;
	for (b = 0; b < 1 << n2; b++)
		if ((adj_[b] & b << n1) == 0)
			ans += cnt[~adj_[b] & (1 << n1) - 1];
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

geppetto.c: In function 'main':
geppetto.c:28:15: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |   adj_[1 << i - n1] = adj[i];
      |             ~~^~~~
geppetto.c:36:36: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   36 |    ans += cnt[~adj_[b] & (1 << n1) - 1];
      |                          ~~~~~~~~~~^~~
geppetto.c:10:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   10 |  scanf("%d%d", &n, &m), n1 = n / 2, n2 = n - n1;
      |  ^~~~~~~~~~~~~~~~~~~~~
geppetto.c:12:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   12 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 80 / 80