Submission #705609

#	Time	Username	Problem	Language	Result	Execution time	Memory
705609		finn__	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	1417 ms	2600 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;

#define N 18
#define MOD 998244353

int64_t g[N], f[1 << N];
bitset<1 << N> is_independent;

int main()
{
    int64_t n, m;
    cin >> n >> m;

    for (size_t i = 0; i < m; i++)
    {
        size_t u, v;
        cin >> u >> v;
        g[u - 1] ^= (1 << (v - 1));
        g[v - 1] ^= (1 << (u - 1));
    }

    for (size_t i = 0; i < 1 << n; i++)
    {
        is_independent[i] = 1;
        for (size_t j = 0; j < n; j++)
            if (i & (1 << j))
                is_independent[i] = is_independent[i] && !(g[j] & i);
    }

    f[0] = 1;
    for (size_t i = 0; i < 1 << n; i++)
    {
        for (size_t j = i; j; j = (j - 1) & i)
            if (is_independent[j])
                f[i] += f[i ^ j] * ((__builtin_popcount(j) & 1) ? 1 : -1);
        f[i] = (f[i] % MOD + MOD) % MOD;
    }

    cout << (((m * f[(1 << n) - 1]) % MOD) * 499122177) % MOD << '\n';
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:15:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   15 |     for (size_t i = 0; i < m; i++)
      |                        ~~^~~
amusementpark.cpp:23:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     for (size_t i = 0; i < 1 << n; i++)
      |                        ~~^~~~~~~~
amusementpark.cpp:26:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   26 |         for (size_t j = 0; j < n; j++)
      |                            ~~^~~
amusementpark.cpp:32:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |     for (size_t i = 0; i < 1 << n; i++)
      |                        ~~^~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37