Submission #1177365

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

amusementpark

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

#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define ll long long
#define f first
#define s second

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using ind_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll MOD = 1e9+7;
int M998 = 998244353;

void solve(int tc_ = 0) {
    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n, vector<int>(n, 0));
    for (int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b; a--; b--;
        adj[a][b] = 1;
        adj[b][a] = 2;
    }
    ll cnt[1 << n][n], dp[1 << n][n];
    for (int b = 0; b < (1 << n); ++b) {
        for (int i = 0; i < n; ++i) {
            cnt[b][i] = dp[b][i] = 0;
        }
    }
    for (int i = 0; i < n; ++i) {
        cnt[0][i] = 1;
    }
    for (int b = 0; b < (1 << n); ++b) {
        for (int i = 0; i < n; ++i) {
            if ((1 << i) & b) continue;
            int num = 0;
            for (int j = 0; j < n; ++j) {
                if (((1 << j) & b) && adj[j][i] == 2) num++;
            }
            int mn = i;
            for (int j = i; j >= 0; --j) {
                if ((1 << j) & b) {
                    if (adj[i][j]) mn = j;
                    else break;
                }
            }
            int c = b ^ (1 << i);
            for (int j = 0; j <= i; ++j) {
                cnt[c][j] = (cnt[c][j] + cnt[b][mn]) % M998;
                dp[c][j] = (dp[c][j] + num * cnt[b][mn] + dp[b][mn]) % M998;
            }
        }
    }
    // for (int b = 0; b < (1 << n); ++b) {
    //     cerr << b << '\n';
    //     for (int i = 0; i < n; ++i) {
    //         cerr << cnt[b][i] << ' ' << dp[b][i] << '\n';
    //     }
    // }
    cout << dp[(1 << n) - 1][0] << '\n';
}

void setio(string s = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("err.txt", "w", stderr);
    freopen("out.txt", "w", stdout);
    #else
    if (sz(s)) {
        freopen((s+".in").c_str(), "r", stdin);
        freopen((s+".out").c_str(), "w", stdout);
    }
    #endif
}
 
int32_t main() {
    setio();

    int t = 1;
    // cin >> t; 
    for (int i = 0; i < t; ++i) solve(i);
 
    cerr << "Time : " << (double) clock() / CLOCKS_PER_SEC << "s" << endl;
    return 0;
}   

Compilation message (stderr)

amusementpark.cpp: In function 'void setio(std::string)':
amusementpark.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen((s+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
amusementpark.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen((s+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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