Submission #782260

#TimeUsernameProblemLanguageResultExecution timeMemory
782260magicianAmusement Park (CEOI19_amusementpark)C++14
42 / 100
1544 ms170720 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]; int main() { ios::sync_with_stdio(0); cin.tie(0); // freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); cin >> N >> M; for(int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--; b--; adj[a] ^= MASK(b); } // if(N <= 6) // { // vector<pair<int, int>> e; // for(int i = 0; i < N; i++) // for(int j = 0; j < N; j++) // if(BIT(adj[i], j)) // e.push_back(make_pair(i, j)); // 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 = [&](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; // } // else if(N <= 10) { vector<int> p(N); iota(begin(p), end(p), 0); int ans = 0; set<long long> save; do { vector<int> pos(N); for(int i = 0; i < N; i++) { pos[p[i]] = i; } int num = 0; long long mask = 0; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { if(BIT(adj[i], j)) { if(pos[i] > pos[j]) mask ^= MASK(num); num++; } } } if(!save.count(mask)) { save.insert(mask); ans += __builtin_popcountll(mask); } } while(next_permutation(p.begin(), p.end())); 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...