986C - AND Graph - CodeForces Solution

#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, b) for (int i = 0, _b = (b); i < _b; i++)
#define ii pair<int, int>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1LL)
#define ll long long
#define ld long double
#define next ____next
#define prev ____prev
#define left ____left
#define right ___right
#define lcm ___lcm
using namespace std;

template<class M> M myabs(M x) {
        return x < 0 ? -x : x;
}
template<class M1, class M2> bool minimize(M1 &x, const M2 &y) {
        if (x > y) {x = y; return true;} return false;
}
template<class M1, class M2> bool maximize(M1 &x, const M2 &y) {
        if (x < y) {x = y; return true;} return false;
}

const int INF = (int)1e9 + 7;
const ll INFLL = (ll)1e18 + 7LL;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

const int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

struct DisjointSet {
        vector<int> lab;
        int n;
        DisjointSet(int _n = 0) {
            n = _n;
            lab.assign(n + 1, -1);
        }
        int find(int x) {
            return lab[x] < 0 ? x : lab[x] = find(lab[x]);
        }
        void join(int x, int y) {
            x = find(x); y = find(y);
            if (x == y) return;
            if (lab[x] > lab[y]) swap(x, y);
            lab[x] += lab[y];
            lab[y] = x;
        }
};

#define MAX 22

int n, m;
int a[MASK(22) + 1];

void sub1() {
        DisjointSet dsu(m);
        FOR(i, 1, m) FOR(j, 1, m) if ((a[i] & a[j]) == 0) dsu.join(i, j);

        int res = 0;
        FOR(i, 1, m) res += dsu.find(i) == i;
        cout << res;
}

int exist[MASK(22) + 1];
void sub2() {
        DisjointSet dsu(MASK(n));
        FOR(i, 1, m) exist[a[i]] = i;
        FOR(mask, 0, MASK(n) - 1) if (exist[mask] > 0)
        for (int submask = ((MASK(n) - 1) ^ mask); submask > 0; submask = (submask - 1) & ((MASK(n) - 1) ^ mask))
            if (exist[submask] > 0) dsu.join(mask, submask);

        int res = 0;
        FOR(i, 0, MASK(n) - 1) if (exist[i]) res += dsu.find(i) == i;
        cout << res;
}

vector<int> adj[MASK(22) + 1];
bool vis[MASK(22) + 1];
int root[MASK(22) + 1][2];
void sub3() {
        FOR(i, 1, m) exist[a[i]] = i;
        memset(root, -1, sizeof root);
        
        FOR(i, 1, m) if (root[a[i]][0] == -1) {
            queue<int> q; q.push(a[i]);
            root[a[i]][0] = root[a[i]][1] = a[i];

            while (!q.empty()) {
                int u = q.front(); q.pop();
                //cout << u << " " << root[u][1] << "\n";
                //cout << u << " ";
                for (int hihi = ((MASK(n) - 1) ^ u); hihi > 0; hihi -= hihi & -hihi) {
                    int i = __builtin_ctz(hihi);
                    int v = u | MASK(i);
                    if (root[v][1] == -1) {
                        root[v][1] = root[u][1];
                        q.push(v);
                    }
                    //cout << v << "\n";
                }

                int v = (MASK(n) - 1) ^ u;
               //cout << v << "\n";
                if (exist[v] && root[v][0] == -1) {
                    root[v][0] = root[v][1] = root[u][1];
                    q.push(v);
                }
            }
        }
        int res = 0;
        FOR(i, 1, m) if (root[a[i]][0] == a[i]) res++;
        cout << res;
}

void solve() {
        cin >> n >> m;
        FOR(i, 1, m) cin >> a[i];
        //if (m <= 2000) {sub1(); return;}
        //if (n <= 15) {sub2(); return;}
        sub3();
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        #ifndef ONLINE_JUDGE
        freopen("test.inp", "r", stdin);
        //freopen("test.out", "w", stdout);
        #else
        //
        #endif // ONLINE_JUDGE
        int t = 1; //cin >> t;
        while (t--) solve();
}