Submission #405533

#TimeUsernameProblemLanguageResultExecution timeMemory
405533FalconAmusement Park (CEOI19_amusementpark)C++17
63 / 100
3055 ms25296 KiB
#include <vector> #include <array> #include <iostream> #ifdef DEBUG #include "debug.hpp" #endif using namespace std; #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it) #define rep(i, N) for(int i = 0; i < (N); ++i) #define rrep(i, N) for(int i = (N) - 1; i >= 0; --i) #define rep1(i, N) for(int i = 1; i <= (N); ++i) #define rep2(i, s, e) for(int i = (s); i <= (e); ++i) #ifdef DEBUG #define debug(x...) { \ ++dbg::depth; \ string dbg_vals = dbg::to_string(x); \ --dbg::depth; \ dbg::fprint(__func__, __LINE__, #x, dbg_vals); \ } #define light_debug(x) { \ dbg::light = true; \ dbg::dout << __func__ << ":" << __LINE__; \ dbg::dout << " " << #x << " = " << x << endl; \ dbg::light = false; \ } #else #define debug(x...) 42 #define light_debug(x) 42 #endif using ll = long long; template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; } template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; } constexpr int mod{998244353}; int main() { ios_base::sync_with_stdio(false); cin.tie(0); array<bool, 1 << 18> parity; rep(i, 1 << 18) parity[i] = __builtin_popcount(i) % 2 == 0; array<int, 1 << 18> lg; rep(i, 1 << 18) lg[i] = __lg(i); int n, m; cin >> n >> m; vector<vector<bool>> adj(n, vector<bool>(n)); rep(i, m) { int u, v; cin >> u >> v; --u, --v; adj[u][v] = true; } vector<bool> is_independent(1 << n); rep(mask, 1 << n) { is_independent[mask] = true; rep(i, n) if(mask & (1 << i)) rep(j, n) if(adj[i][j] && (mask & (1 << j))) is_independent[mask] = false; } vector<vector<int>> single_cost(n, vector<int>(1 << n)); rep(i, n) rep1(mask, (1 << n) - 1) { single_cost[i][mask] = single_cost[i][mask - (1 << lg[mask])] + adj[lg[mask]][i]; } vector<long long> dp_s(1 << n), dp_c(1 << n); dp_c[0] = 1; vector<int> partial_cost(1 << n); int j, sources; long long t_s, t_c; rep1(mask, (1 << n) - 1) { for(sources = mask & (mask - 1); ; sources = (sources - 1) & mask) { sources = mask - sources; j = lg[sources]; partial_cost[sources] = partial_cost[sources - (1 << j)] + single_cost[j][mask]; if(is_independent[sources]) { t_s = dp_s[mask ^ sources] + dp_c[mask ^ sources] * partial_cost[sources] % mod; dp_s[mask] += parity[sources] ? -t_s : t_s; t_c = dp_c[mask ^ sources]; dp_c[mask] += parity[sources] ? -t_c : t_c; } sources = mask - sources; if(sources == 0) break; } ((dp_c[mask] %= mod) += mod) %= mod; ((dp_s[mask] %= mod) += mod) %= mod; for(sources = mask; sources > 0; sources = (sources - 1) & mask) partial_cost[sources] = 0; } cout << dp_s.back() << '\n'; #ifdef DEBUG dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC << "ms" << endl; #endif 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...