Submission #674821

#	Time	Username	Problem	Language	Result	Execution time	Memory
674821		vovik	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2728 ms	4652 KiB

amusementpark

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

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