Submission #741114

#TimeUsernameProblemLanguageResultExecution timeMemory
741114AverageAmogusEnjoyerAmusement Park (CEOI19_amusementpark)C++17
0 / 100
1 ms212 KiB
/* ID: dalpone1 TASK: amusementpark LANG: C++ */ #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define pb push_back #define ll long long #define nl '\n' const int N = 19, mod = 998244353; int n, m; ll dp[1 << N], compute[N]; vector<int> adj[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (ll i = 1; i < N; i++) { compute[i] = (1 << (i-1)) * i; } for (int i = 0, s, e; i < m; i++) { cin >> s >> e; s--, e--; adj[s].pb(e); adj[e].pb(s); } int sz = 1 << n; for (int i = 0; i < sz; i++) { ll add = 0; for (int j = 0; j < n; j++) { if ((i & (1 << j)) == 0) continue; int count = 0; for (int k: adj[j]) if ((1 << k) & i) count++; add += compute[count]; dp[i] = ((dp[i] % mod) + (dp[i ^ (1 << j)] % mod)) % mod; } dp[i] = ((dp[i] % mod) + (add % mod) / 2) % mod; } cout << dp[sz-1]; }
#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...