Submission #439172

#	Time	Username	Problem	Language	Result	Execution time	Memory
439172		prvocislo	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2870 ms	308836 KiB

amusementpark

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

const ll mod = 998244353; // staci ho pouzit len raz, na konci
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> e(n);
    for (int i = 0, a, b; i < m; i++) 
    {
        cin >> a >> b;
        a--, b--;
        e[a] |= (1 << b);
        e[b] |= (1 << a);
    }
    vector<map<int, ll> > dp(1 << n); // dp[A][B]
    dp[0][(1 << n) - 1] = 1;
    for (int a = 0; a < (1 << n); a++)
    {
        for (const pair<int, ll> &i : dp[a])
        {
            int b = i.first; ll val = i.second;
            for (int c = 0; c < n; c++)
            {
                if (!((1 << c)&b)) continue;
                int nwa = a|(1 << c);
                int bad = ((1 << (c + 1))-1)&b;
                int in0 = e[c] & ((1 << n) - 1 - a);
                int nwb = (b ^ bad) | in0;
                dp[nwa][nwb] += dp[a][b];
            }
        }
    }
    cout << (dp[(1 << n) - 1][0] * (ll)m / 2ll) % mod << "\n";
    return 0;
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:26:33: warning: unused variable 'val' [-Wunused-variable]
   26 |             int b = i.first; ll val = i.second;
      |                                 ^~~

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