# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
395147 | 2021-04-27T22:06:02 Z | rainboy | Geppetto (COCI15_geppetto) | C | 1 ms | 284 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | Output isn't correct |
2 | Incorrect | 1 ms | 204 KB | Output isn't correct |
3 | Incorrect | 1 ms | 204 KB | Output isn't correct |
4 | Incorrect | 1 ms | 280 KB | Output isn't correct |
5 | Incorrect | 1 ms | 204 KB | Output isn't correct |
6 | Incorrect | 1 ms | 284 KB | Output isn't correct |
7 | Incorrect | 1 ms | 204 KB | Output isn't correct |
8 | Incorrect | 1 ms | 204 KB | Output isn't correct |
9 | Incorrect | 1 ms | 204 KB | Output isn't correct |
10 | Incorrect | 1 ms | 204 KB | Output isn't correct |