Submission #782260

#	Time	Username	Problem	Language	Result	Execution time	Memory
782260		magician	Amusement Park (CEOI19_amusementpark)	C++14	42 / 100	1544 ms	170720 KiB

amusementpark

#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;
        }
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37