Submission #1262229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262229		euclid	Amusement Park (CEOI19_amusementpark)	C++20	7 / 100	0 ms	328 KiB

amusementpark

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vl vector<ll>

int n, m;
const int MN = 21, MS = (1<<18)+7, MOD = 998244353;
bool adj[MN][MN];
pll dp[MS][MN]; //dp[s][j]: total cost of all legal proposals and the number of
//legal proposals such that the lowest point is j. if there are multiple possible
//lowest points, the one with the smallest index is considered the lowest

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u][v] = true;
    }
    for(int i = 0; i < n; i++) dp[1<<i][i+1] = {0, 1};
    for(int s = 1; s < 1<<n; s++) {
        if(__builtin_popcount(s) == 1) continue;
        for(int j = 1; j <= n; j++) {
            if(!((1<<(j-1))&s)) continue;
            int cnt = 0;
            for(int i = 1; i <= n; i++)
                if(s&(1<<(i-1)) && adj[j][i]) cnt++;
//            if(s == 3 && j == 2) cout << cnt << '\n';
            for(int i = 1; i <= n; i++) {
                if(s&(1<<(i-1)) && i != j) {
                    if(adj[i][j] || adj[j][i] || i > j) {
                        int ss = s^(1<<(j-1));
                        dp[s][j].fi += dp[ss][i].se*cnt+dp[ss][i].fi;
                        dp[s][j].se += dp[ss][i].se;
                        dp[s][j].fi %= MOD, dp[s][j].se %= MOD;
                    }
                }
            }
        }
    }
//    cout << dp[1][1].fi << ' ' << dp[1][1].se << '\n';
//    cout << dp[3][2].fi << ' ' << dp[3][2].se << '\n';
    ll tot = 0;
    for(int i = 1; i <= n; i++) tot = (tot+dp[(1<<n)-1][i].fi)%MOD;
    cout << tot << '\n';

}

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