oj.uz

Submission #1095456

# Submission time Handle Problem Language Result Execution time Memory
1095456 2024-10-02T09:26:46 Z gyg Amusement Park (CEOI19_amusementpark) C++17
7 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array 
#define vct vector 
const int MX_N = 18 + 2, MD = 998244353;

int n, m;
arr<arr<bool, MX_N>, MX_N> adj;

int md(int x) { return (x + MD) % MD; }
int expn(int x, int y) {
    if (y == 0) return 1;
    int ans = expn(x, y / 2);
    ans = md(ans * ans);
    if (y % 2 == 1) ans = md(ans * x);
    return ans;
}
int inv(int x) { return expn(x, MD - 2); }

arr<bool, 1 << MX_N> indp;
arr<int, 1 << MX_N> mltp;
void prcmp() {
    indp[0] = true;
    for (int msk = 1; msk < (1 << n); msk++) {
        for (int u = 1; u <= n; u++) {
            if (!(msk & (1 << (u - 1)))) continue;
            indp[msk] = indp[msk ^ (1 << (u - 1))];
            for (int v = 1; v <= n; v++) {
                if (!(msk & (1 << (v - 1)))) continue;
                if (v == u) continue;
                if (adj[u][v]) indp[msk] = false;
            }
            break;
        }
    }

    for (int msk = 0; msk < (1 << n); msk++) {
        int sz = 0;
        for (int u = 1; u <= n; u++) sz += (bool) (msk & (1 << (u - 1)));
        mltp[msk] = (sz % 2 == 1) ? 1 : md(-1);
    }
}

arr<int, MX_N> dp;
void cmp() {
    dp[0] = 1;
    for (int msk = 1; msk < (1 << n); msk++) 
        for (int sb_msk = msk; sb_msk != 0; sb_msk = (sb_msk - 1) & msk) 
            if (indp[sb_msk]) dp[msk] = md(dp[msk] + md(mltp[sb_msk] * dp[msk ^ sb_msk]));
}

signed main() {
    // freopen("prk.in", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u][v] = adj[v][u] = true;
    }

    prcmp();
    cmp();
    
    int ans = md(dp[(1 << n) - 1] * md(m * inv(2)));
    cout << ans << endl;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -