oj.uz

Submission #395148

# Submission time Handle Problem Language Result Execution time Memory
395148 2021-04-27T22:11:34 Z rainboy Geppetto (COCI15_geppetto) C
80 / 80
 1 ms 208 KB 
#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

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.0 / 80.0

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