fork download
copy 
  1. #include<bits/stdc++.h> //NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. using pii = pair<int, int>;
  8. using pipii = pair<int, pii>;
  9. template <class T> using heapmin = priority_queue<T, vector<T>, greater<T>>;
  10. const int N = 2e5 + 5;
  11. int n, a[N];
  12. int par[N];
  13. int findPar(int u) {
  14.     if (u == par[u]) return u;
  15.     return par[u] = findPar(par[u]);
  16. }
  17. bool joint(int u, int v) {
  18.     u = findPar(u);
  19.     v = findPar(v);
  20.     if (u == v) return 0;
  21.     par[v] = u;
  22.     return 1;
  23. }
  24.  
  25. namespace sub1 {
  26. struct Edge{
  27.     int u, v, w;
  28. };
  29. vector<Edge> E;
  30. void solve () {
  31.     for (int i = 1; i <= n; i++) {
  32.         for (int j = i + 1; j <= n; j++) {
  33.             E.push_back({i, j, a[i] ^ a[j]});
  34.         }
  35.     }
  36.     sort(E.begin(), E.end(), [&] (const Edge &x, const Edge &y) {
  37.         return x.w < y.w;
  38.     });
  39.     int ans = 0;
  40.     for (int i = 1; i <= n; i++) {
  41.         par[i] = i;
  42.     }
  43.     int cnt = 0;
  44.     for (Edge &e: E) {
  45.         int u = e.u, v = e.v, w = e.w;
  46.         if (joint(u, v)) ans += w, cnt++;
  47.         if (cnt == n - 1) break;
  48.     }
  49.     cout << ans;
  50. }
  51. };
  52.  
  53. namespace subfull {
  54. const int LG = 29;
  55. int ans = 0;
  56. bool vis[N];
  57. struct Node {
  58.     int child[2];
  59.     int cnt, exist;
  60. };
  61. vector<Node> Trie;
  62. int newNode() {
  63.     int id = Trie.size();
  64.     Node tmp;
  65.     tmp.child[0] = tmp.child[1] = -1;
  66.     tmp.cnt = tmp.exist = 0;
  67.     Trie.push_back(tmp);
  68.     // cerr << id << "\n";
  69.     return id;
  70. }
  71. void addNum(int x, int t) {
  72.     int pos = 0;
  73.     for (int i = 29; i >= 0; i--) {
  74.         Trie[pos].cnt++;
  75.         int c = ((x >> i) & 1);
  76.         if (Trie[pos].child[c] == -1) {
  77.             int id = newNode();
  78.             Trie[pos].child[c] = id;
  79.         }
  80.         // cerr << x << " " << t << "  "<< c << ": " << pos << " -> " << Trie[pos].child[c] << "\n";
  81.         pos = Trie[pos].child[c];
  82.     }
  83.     Trie[pos].cnt++;
  84.     Trie[pos].exist = t;
  85. }
  86.  
  87. void delNum(int x) {
  88.     int pos = 0;
  89.     for (int i = 29; i >= 0; i--) {
  90.         // cerr << "DEL: " << pos << " " << x << " " << i << " " << Trie[pos].cnt << " -> ";
  91.         Trie[pos].cnt--;
  92.         // cerr << "CAI DEO J MA TU 2 XUONG CON ME SO 0 V: ";
  93.         // cerr << Trie[pos].cnt << "\n";
  94.         int c = ((x >> i) & 1);
  95.         pos = Trie[pos].child[c];
  96.     }
  97.     Trie[pos].cnt--;
  98.     Trie[pos].exist = 0;
  99.     // cerr << "DEL: "<< pos << " " << x  << " " << Trie[pos].cnt << "\n";
  100. }
  101. int findXor(int x) {
  102.     int pos = 0;
  103.     // cerr << "CNT: " << Trie[pos].cnt << "\n";
  104.     for (int i = 29; i >= 0; i--) {
  105.  
  106.         int c = (x >> i & 1);
  107.         // cerr << "finxor: " << x << " " << pos << " | " << i << " " << c << " -> ";
  108.         if (Trie[pos].child[c] == -1 || Trie[Trie[pos].child[c]].cnt == 0) c = (c ^ 1);
  109.         if (Trie[pos].child[c] == -1) return 0;
  110.         pos = Trie[pos].child[c];
  111.         // cerr << c << " " << pos << '\n';
  112.     }
  113.     return Trie[pos].exist;
  114. }
  115. void solve() {
  116.     if (n == 1) return cout << 0, void();
  117.     newNode();
  118.     for (int i = 2; i <= n; i++) addNum(a[i], i);
  119.  
  120.     int tid = findXor(a[1]);
  121.     // cerr << tid << '\n';
  122.     int rem = 1;
  123.     vis[1] = 1;
  124.     heapmin<pipii> Q;
  125.     Q.push({a[1] ^ a[tid], {1, tid}});
  126. //    for (int i = 1; i <= n; i++) cerr << a[i] << " "; cerr << '\n';
  127.     while(rem < n && !Q.empty()) {
  128.         int old = Q.top().ft, rt = Q.top().sc.ft, nxt = Q.top().sc.sc;
  129.         Q.pop();
  130.     //    cerr << old << " " << rt << " " << nxt << '\n';
  131.         if (vis[nxt]) {
  132.             int id = findXor(a[rt]);
  133.             if (id) Q.push({a[rt] ^ a[id], {rt, id}});
  134.             continue;
  135.         }
  136.         vis[nxt] = 1;
  137.         delNum(a[nxt]);
  138.         ans += old;
  139.         rem++;
  140.  
  141.         int id = findXor(a[nxt]);
  142.     //    cerr << nxt << " -> " << id << '\n';
  143.         if (id) Q.push({a[nxt] ^ a[id], {nxt, id}});
  144.         id = findXor(a[rt]);
  145.     //    cerr << rt << " -> " << id << '\n';
  146.         if (id) Q.push({a[rt] ^ a[id], {rt, id}});
  147.     }
  148.     cout << ans;
  149. }
  150. };
  151.  
  152. signed main() {
  153.     cin.tie(NULL)->sync_with_stdio(false); cout.tie(NULL);
  154.     if (ifstream("XOR.INP")) {
  155.         freopen("XOR.INP", "r", stdin);
  156.         freopen("XOR.OUT", "w", stdout);
  157.     }
  158.     cin >> n;
  159.     vector<int> tmp(n); for (int i = 1; i <= n; i++) cin >> tmp[i - 1];
  160.     sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
  161.     n = tmp.size();
  162.     for (int i = 1; i <= n; i++) a[i] = tmp[i - 1];
  163.  
  164.     // if (n <= 3000) return sub1::solve(), 0;
  165.     return subfull::solve(), 0;
  166.     return 0;
  167. }
  168.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/04j8kB
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!