Proficient.
Put your skills to the test.

Problem summary

Find the minimum spanning tree weight of the complete graph whose vertex values are A[i] and whose edge (i,j) has weight A[i] bitwise-OR A[j].

Constraints

1 ≤ N ≤ 2^23; 0 ≤ A[i] < 2^B; B ≤ 23.

Worked example

An independently prepared example for this explanation.

3 4
2 5 6

13

Solution analysis

1. Group equal values first. Keep one vertex for each distinct value v, and add (frequency[v]−1)·v to the answer. Equal vertices can be attached to their representative at cost v; connecting one elsewhere can never be cheaper because v OR x ≥ v.
2. Process every mask w in numerical order. All vertices whose values are submasks of w must become connected using edges of weight at most w. For each immediate submask w with one set bit deleted, a previously stored representative stands for all present values below that submask. Include the vertex whose value is exactly w, if present. Join these representatives with DSU, adding w for each successful union; save any one representative for w.
3. This is an implicit Kruskal scan. Any two submasks a,b of w in different components have a OR b = w: a smaller OR would already have connected them at an earlier mask. Thus each successful union really can use an edge of the charged weight. There are only popcount(w) immediate submasks, even when w has exponentially many submasks.
4. For 2,5,6, mask 6 connects values 2 and 6 with cost 6. Mask 7 first brings the component containing 5 together with that component, costing 7. The total is 13. Empty masks keep representative −1 and add no edges.

Why it works

For duplicates, contract all vertices of one value v. Each connection internal to that group costs v, while any external edge has weight at least v. In an MST, exchanging external connections along paths permits the group to be connected internally without increasing weight; its duplicates contribute (frequency−1)v. For distinct values, induct on w: all vertices whose value is a submask of every smaller processed mask are connected. Every proper submask of w lies below an immediate submask, so the selected representatives cover every relevant component. If two such components had an edge of weight below w they would already be joined when that OR mask was processed. Their edge therefore has weight w. The algorithm performs exactly the unions Kruskal needs at that weight. Induction gives a spanning tree of minimum weight.

Watch out. Duplicates contribute their value, not zero. A representative denotes a connected set of present submasks and need not equal its mask. Use 64-bit totals.

Grader function only; no main. Compile with a separate local harness using the stated signature.

#include<vector>
#include<numeric>
#include<utility>
class Components{
    std::vector<int>parent,size;
    public:
    explicit Components(int n):parent(n),size(n,1){
        std::iota(parent.begin(),parent.end(),0);
    }
    int find(int x){
        while(parent[x]!=x){
            parent[x]=parent[parent[x]];
            x=parent[x];
        }
        return x;
    }
    bool join(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b){
            return false;
        }
        if(size[a]<size[b]){
            std::swap(a,b);
        }
        parent[b]=a;
        size[a]+=size[b];
        return true;
    }
};
long long solve(std::vector<int>A,int B){
    int limit=1<<B;
    std::vector<int>representative(limit,-1);
    long long answer=0;
    int distinct=0;
    for(int value:A){
        if(representative[value]==-1){
            representative[value]=distinct++;
        }
        else{
            answer+=value;
        }
    }
    Components components(distinct);
    for(int mask=0;mask<limit;++mask){
        int root=representative[mask];
        // All present submasks of each smaller mask are already connected.
        for(int bits=mask;bits!=0;bits&=bits-1){
            int bit=bits&-bits;
            int other=representative[mask^bit];
            if(other==-1){
                continue;
            }
            if(root==-1){
                root=other;
            }
            else if(components.join(root,other)){
                answer+=mask;
            }
        }
        representative[mask]=root;
    }
    return answer;
}