Kickstart Round G: Problem B

Abridged problem statement

To N cards, each of the front and back are red and blue, each with a number, you can choose two cards at a time, you can choose a card with a blue face number and the other card red face The result is added to your score (initial score = 0), then discard a card and put back a card until you are left with just 1 card

Constraints

1 ≤ T ≤ 100.
1 ≤ R_i ≤ 10⁹.
1 ≤ B_i ≤ 10⁹.

Small dataset

2 ≤ N ≤ 5.

Large dataset

2 ≤ N ≤ 100.

Approach  

On careful observation we observethat the minimum requirement for the sum of the weights and bounds is actually the minimum spanning tree formed by n points. Kruskal can be used to construct the MST

Code

#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <tuple>
#include <algorithm>

using namespace std;

int red[105], blue[105];
int union_find[105];

int find(int x)
{
  return union_find[x] == x?x :union_find[x] = find(union_find[x]);
}
bool merge(int a, int b)
{
  a = find(a);
  b = find(b);
  if (a != b)
  {
    union_find[a] = b;
    return true;
  }
  return false;
}

int main(){

freopen("B-large-practice.in", "r", stdin);
freopen("output-large.txt", "w", stdout);

  int t, n;
  cin>>t;

  for(int cases = 1; cases<=t; cases++){
  vector<tuple<int, int, int> > res;
  cin>>n;
  for(int i=0; i<n; i++) cin>>red[i];
  for(int i=0; i<n; i++) cin>>blue[i];

  for(int i=0; i<n; i++){
    for(int j=i+1; j<n; j++){
      res.emplace_back(min(red[i]^blue[j], red[j]^blue[i]), i, j);
    }
    union_find[i]=i;
  }

  sort(res.begin(), res.end());

  long long ans =0;

  for (auto i : res)
  {
    int u, v, w;
    tie(w, u, v) = i;
    if (merge(u, v))
    {
      ans += w;
    }
  }

  cout << "Case #"<<cases<<": "<<ans<<endl;

  }
  return 0;
}