Submission #348744

#	Time	Username	Problem	Language	Result	Execution time	Memory
348744		doowey	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	1812 ms	234988 KiB

amusementpark

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 18;
const int MOD = 998244353;
int mask[N];
map<int,int> dp[1<<N];

void add(int &a, int b){
    a += b;
    a %= MOD;
}

int main(){
    fastIO;
    int n,m;
    cin >> n >> m;
    int u, v;
    for(int i = 1; i <= m; i ++ ){
        cin >> u >> v;
        u--;
        v--;
        mask[u] |= (1 << v);
        mask[v] |= (1 << u);
    }
    dp[0][(1<<n)-1]=1;
    int cur, msk;
    int val;
    int nah;
    for(int i = 0 ; i < (1 << n); i ++ ){
        for(auto x : dp[i]){
            cur = i;
            msk = x.fi;
            val = x.se;
            for(int nx = 0 ; nx < n; nx ++ ){
                if((msk & (1 << nx))){
                    nah = (msk & (((1<<n)-1)-((1<<(nx+1))-1)));
                    nah = (nah | ((mask[nx]|i)^i));
                    add(dp[(i|(1<<nx))][nah],val);
                }
            }
        }
    }
    int sol = dp[(1<<n)-1][0];
    sol = (sol * 1ll * m) % MOD;
    sol = (sol * 1ll * (MOD+1)/2) % MOD;
    cout << sol << "\n";
    return 0;
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:36:9: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
   36 |     int cur, msk;
      |         ^~~

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