Submission #782056

#TimeUsernameProblemLanguageResultExecution timeMemory
782056magicianAmusement Park (CEOI19_amusementpark)C++14
19 / 100
3083 ms340 KiB
#include<bits/stdc++.h> #define MASK(x) (1LL << (x)) #define BIT(x, i) (((x) >> (i)) & 1) using namespace std; const int MAXN = 18; const int MOD = 998244353; int N, M; int adj[MAXN]; vector<pair<int, int>> e; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> M; for(int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--; b--; adj[a] ^= MASK(b); e.push_back(make_pair(a, b)); } //if(M <= 20) { int ans = 0; for(int mask = 0; mask < MASK(M); mask++) { vector<int> new_adj(N, 0); for(int i = 0; i < M; i++) { if(BIT(mask, i)) new_adj[e[i].second] ^= MASK(e[i].first); else new_adj[e[i].first] ^= MASK(e[i].second); } vector<int> vis(N, 0); bool good = true; function<void(int)> dfs; dfs = [&](int u) { if(!good) return; vis[u] = 1; for(int i = 0; i < N; i++) { if(BIT(new_adj[u], i) && vis[i] == 1) { good = false; return; } } for(int i = 0; i < N; i++) { if(BIT(new_adj[u], i) && vis[i] == 0) { dfs(i); if(!good) return; } } vis[u] = 2; }; for(int i = 0; i < N; i++) if(vis[i] == 0) dfs(i); if(good) (ans += __builtin_popcount(mask)) %= MOD; } cout << ans; } }
#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...