fork download
copy 
  1.  
  2. #include<bits/stdc++.h> //NeOWami
  3. using namespace std;
  4.  
  5. #define ft first
  6. #define sc second
  7. #define int long long
  8. using pii = pair<int, int>;
  9. const int N = 2e5 + 5;
  10. const int inf = 1e18;
  11. const int LG = 29;
  12.  
  13. int n, a[N], ans = 0;
  14.  
  15. vector<int> comp[N];
  16. int par[N];
  17. int bestW[N], bestV[N], bestU[N];
  18. int findPar(int u) {
  19.     if (u == par[u]) return u;
  20.     return par[u] = findPar(par[u]);
  21. }
  22. bool joint(int u, int v) {
  23.     u = findPar(u);
  24.     v = findPar(v);
  25.     if (u == v) return 0;
  26.     par[v] = u;
  27.     return 1;
  28. }
  29.  
  30. bool vis[N];
  31. struct Node {
  32.     int child[2];
  33.     int cnt, exist;
  34. };
  35. vector<Node> Trie;
  36. int newNode() {
  37.     int id = Trie.size();
  38.     Node tmp;
  39.     tmp.child[0] = tmp.child[1] = -1;
  40.     tmp.cnt = tmp.exist = 0;
  41.     Trie.push_back(tmp);
  42.     return id;
  43. }
  44. void buildTrie() {
  45.     newNode();
  46. }
  47. void addNum(int x, int t) {
  48.     int pos = 0;
  49.     for (int i = 29; i >= 0; i--) {
  50.         Trie[pos].cnt++;
  51.         int c = ((x >> i) & 1);
  52.         if (Trie[pos].child[c] == -1) {
  53.             int id = newNode();
  54.             Trie[pos].child[c] = id;
  55.         }
  56.         pos = Trie[pos].child[c];
  57.     }
  58.     Trie[pos].cnt++;
  59.     Trie[pos].exist = t;
  60. }
  61.  
  62. void delNum(int x) {
  63.     int pos = 0;
  64.     for (int i = 29; i >= 0; i--) {
  65.         Trie[pos].cnt--;
  66.         int c = ((x >> i) & 1);
  67.         pos = Trie[pos].child[c];
  68.     }
  69.     Trie[pos].cnt--;
  70.     Trie[pos].exist = 0;
  71. }
  72. int findXor(int x) {
  73.     int pos = 0;
  74.     for (int i = 29; i >= 0; i--) {
  75.         int c = (x >> i & 1);
  76.         if (Trie[pos].child[c] == -1 || Trie[Trie[pos].child[c]].cnt == 0) c = (c ^ 1);
  77.         if (Trie[pos].child[c] == -1) return 0;
  78.         pos = Trie[pos].child[c];
  79.     }
  80.     return Trie[pos].exist;
  81. }
  82.  
  83.  
  84. signed main() {
  85.     cin.tie(NULL)->sync_with_stdio(false); cout.tie(NULL);
  86.     if (ifstream("XOR.INP")) {
  87.         freopen("XOR.INP", "r", stdin);
  88.         freopen("XOR.OUT", "w", stdout);
  89.     }
  90.     cin >> n;
  91.     vector<int> tmp(n); for (int i = 1; i <= n; i++) cin >> tmp[i - 1];
  92.     sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
  93.     n = tmp.size();
  94.     for (int i = 1; i <= n; i++) a[i] = tmp[i - 1];
  95.  
  96.     //Borůvka 
  97.     for (int i = 1; i <= n; i++) par[i] = i;
  98.     while(1) {
  99.         vector<int> roots;
  100.         for (int i = 1; i <= n; i++) {
  101.             int r = findPar(i);
  102.             comp[r].push_back(i);
  103.         }
  104.         for (int r = 1; r <= n; r++) if (comp[r].size()) roots.push_back(r);
  105.         if (roots.size() <= 1) break;
  106.         Trie.clear();
  107.         buildTrie();
  108.         for (int i = 1; i <= n; i++) addNum(a[i], i);
  109.  
  110.         for (int r : roots){
  111.             for (int u: comp[r]) delNum(a[u]);
  112.             bestW[r] = inf;
  113.             for (int u: comp[r]){
  114.                 int v = findXor(a[u]);
  115.                 if (v <= 0) continue;
  116.                 int w = a[u] ^ a[v];
  117.                 if (w < bestW[r]){
  118.                     bestW[r] = w;
  119.                     bestU[r] = u;
  120.                     bestV[r] = v;
  121.                 }
  122.             }
  123.             for (int u: comp[r]) addNum(a[u], u);
  124.         }
  125.  
  126.         for (int r: roots) {
  127.             comp[r].clear();
  128.             if (bestW[r] != inf) {
  129.                 if (joint(bestU[r], bestV[r])) ans += bestW[r];
  130.             }
  131.         }
  132.     }
  133.     cout << ans;
  134.     return 0;
  135. }
  136.  
  137.  
Success #stdin #stdout 0.01s 10272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/x2wkjF
(Borůvka + trie đếm + DSU)
O(n · 30 · log n) (≈ O(n log A log n)
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!