Submission #313775

#	Time	Username	Problem	Language	Result	Execution time	Memory
313775		jhnah917	Amusement Park (CEOI19_amusementpark)	C++14	63 / 100	3081 ms	165380 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 pw_2_15 = 32768;
const int pw_3_18 = 387420489;
const int mod = 998244353;
int pw[22];

int n, m, bit[22];
vector<int> g[22];
map<p, ll> dp;

bool in(int Set, int Elem){
    return (Set & (1 << Elem)) != 0;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    pw[0] = 1; for(int i=1; i<22; i++) pw[i] = pw[i-1] * 3;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int s, e; cin >> s >> e; s--; e--;
        g[s].push_back(e); g[e].push_back(s);
        bit[s] |= (1 << e); bit[e] |= (1 << s);
    }
    
    dp[p(0, 0)] = 1;
    for(auto i : dp){
        int a = i.x.x, b = i.x.y; ll cnt = i.y;
        for(int j=0; j<n; j++) if(!in(a|b, j)) {
            int a_ = (a | (1 << j));
            int b_ = ((b | ((1<<j)-1)) & ~bit[j] & ~a);
            dp[p(a_, b_)] = (cnt + dp[p(a_, b_)]) % mod;
        }
    }
    ll res = dp[p((1<<n)-1, 0)];
    res = res * m % mod * (mod/2+1) % mod;
    cout << res;
}

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