Submission #313796

#	Time	Username	Problem	Language	Result	Execution time	Memory
313796		jhnah917	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	2029 ms	3960 KiB

amusementpark

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
const int mod = 998244353;

int n, m, cnt[1<<18];
bool g[22][22], chk[1<<18];
ll dp[1<<18];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int s, e; cin >> s >> e; s--; e--;
        g[s][e] = g[e][s] = 1;
    }
    for(int i=0; i<(1<<n); i++){
        for(int j=0; j<n; j++) if(i & (1 << j)) {
            for(int k=j+1; k<n; k++) if(i & (1 << k)) {
                if(g[j][k]){ chk[i] = 1; break; }
            }
            if(chk[i]) break;
        }
    }
    
    dp[0] = 1;
    for(int i=1; i<(1<<n); i++) cnt[i] = cnt[i^(i&-i)] + 1;
    for(int i=1; i<(1<<n); i++){
        for(int j=i; j; j=(i&(j-1))) if(!chk[j]) {
            if(cnt[j] & 1) dp[i] += dp[i^j];
            else dp[i] = dp[i] -= dp[i^j];
            if(dp[i] < 0) dp[i] += mod;
            if(dp[i] >= mod) dp[i] %= mod;
        }
    }
    cout << dp[(1<<n)-1] * m % mod * (mod/2+1) % mod;
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:37:24: warning: operation on 'dp[i]' may be undefined [-Wsequence-point]
   37 |             else dp[i] = dp[i] -= dp[i^j];
      |                  ~~~~~~^~~~~~~~~~~~~~~~~~

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