Submission #670210

#	Time	Username	Problem	Language	Result	Execution time	Memory
670210		Alexandruabcde	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	2859 ms	1780 KiB

amusementpark

#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 998244353;
constexpr int INVMOD2 = 499122177;
constexpr int NMAX = 18;
constexpr int SMAX = (1<<NMAX);

int N, M;

bool edge[NMAX][NMAX];
bool good[SMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= M; ++ i ) {
        int x, y;
        cin >> x >> y;

        --x, --y;

        edge[x][y] = true;
    }
}

vector <int> V;
void Precompute () {
    for (int mask = 0; mask < (1<<N); ++ mask ) {
        V.clear();
        for (int i = 0; i < N; ++ i )
            if ((mask&(1<<i))) V.push_back(i);

        bool ok = true;
        for (int i = 0; i < V.size(); ++ i ) {
            for (int j = 0; j < V.size(); ++ j ) {
                if (i == j) continue;

                ok &= (!edge[V[i]][V[j]]);
            }
        }

        good[mask] = ok;
    }
}

int dp[SMAX];

void Add (int &x, int y) {
    x += y;

    if (x < 0) x += MOD;
    if (x >= MOD) x -= MOD;
}

void ComputeFor (int mask, int k, int mask_take, int last_pos) {
    if (k > 0) {
        int sgn = (k % 2 == 1 ? 1 : -1);

        if (good[mask_take])
            Add(dp[mask], sgn * dp[mask^mask_take]);
    }

    if (last_pos == V.size()-1) return;

    for (int i = last_pos+1; i < V.size(); ++ i )
        ComputeFor(mask, k+1, (mask_take^(1<<V[i])), i);
}

void Solve () {
    dp[0] = 1;

    for (int mask = 1; mask < (1<<N); ++ mask ) {
        V.clear();
        for (int i = 0; i < N; ++ i )
            if ((mask&(1<<i))) V.push_back(i);

        ComputeFor(mask, 0, 0, -1);
    }

    cout << ((1LL * M * INVMOD2) % MOD * 1LL * dp[(1<<N)-1]) % MOD << '\n';
}

int main () {
    Read();
    Precompute();
    Solve();

    return 0;
}

Compilation message (stderr)

amusementpark.cpp: In function 'void Precompute()':
amusementpark.cpp:39:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int i = 0; i < V.size(); ++ i ) {
      |                         ~~^~~~~~~~~~
amusementpark.cpp:40:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             for (int j = 0; j < V.size(); ++ j ) {
      |                             ~~^~~~~~~~~~
amusementpark.cpp: In function 'void ComputeFor(int, int, int, int)':
amusementpark.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     if (last_pos == V.size()-1) return;
      |         ~~~~~~~~~^~~~~~~~~~~~~
amusementpark.cpp:70:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = last_pos+1; i < V.size(); ++ i )
      |                              ~~^~~~~~~~~~

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