Submission #1033418

#TimeUsernameProblemLanguageResultExecution timeMemory
1033418codefoxAmusement Park (CEOI19_amusementpark)C++14
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC target("popcnt") #pragma GCC optimize("Ofast") #define int long long #define pii pair<int, int> const int mod = 998244353; int32_t main() { int n, m; cin >> n >> m; vector<bitset<20>> graph(n, 0); vector<bitset<20>> dgraph(n, 0); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; b--; graph[a][b] = 1; dgraph[a][b] = 1; dgraph[b][a] = 1; } int N = 1<<n; vector<pii> dp(N, {0,0}); dp[0] = {1, 0}; for (int i = 0; i < N; i++) { for (int j = 0; j < n; j++) { if (i&(1<<j)) continue; int b = 0; for (int k = 0; k < j; k++) { if (!dgraph[k][j] && (i&(1<<k))) b = 1; } if (b) continue; int d = (graph[j]&(bitset<20>(i))).count(); dp[i+(1<<j)].first += dp[i].first; dp[i+(1<<j)].first%=mod; dp[i+(1<<j)].second += dp[i].second+dp[i].first*d; dp[i+(1<<j)].second%=mod; } } cout << dp[N-1].second; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...