Submission #674810

#	Time	Username	Problem	Language	Result	Execution time	Memory
674810		vovik	Amusement Park (CEOI19_amusementpark)	C++17	63 / 100	3026 ms	4624 KiB

amusementpark

#include <bits/stdc++.h>
long long dp[1 << 18], g[18][18], babyTron[1 << 18];
int main() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 0, x, y; i < m && std::cin >> x >> y; ++i) g[x - 1][y - 1] = true;
    for (int m4sk = 1; m4sk < 1 << n; ++m4sk) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) babyTron[m4sk] |= g[i][j] && (m4sk >> j & 1) && (m4sk >> i & 1);
    for (int m4sk = 1; (dp[0] = 1) && m4sk < 1 << n; ++m4sk) for (int m3sk = m4sk; m3sk; m3sk = (m3sk - 1) & m4sk) (dp[m4sk] += dp[m4sk ^ m3sk] * std::array<int, 2>{-1, 1}[__builtin_popcount(m3sk) & 1] * !babyTron[m3sk]) %= 998244353ll;
    std::cout << (dp[(1 << n) - 1] * m % 998244353ll * ((998244353ll + 1) / 2) % 998244353ll + 998244353ll) % 998244353ll << '\n';
}

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