fork download
copy 
  1. /*
  2.     Problem: "Arun-sir-and-his-girlfriend"
  3.     
  4.     Solution: sort + implicit prefix tree + binary search, O(n * log(n) * WORD_WIDTH)
  5. */
  6.  
  7. #include <iostream>
  8. #include <vector>
  9. #include <algorithm>
  10. #include <cassert>
  11. #include <functional>
  12.  
  13. struct Edge {
  14.     int vertex, cost;
  15. };
  16.  
  17. int main() {
  18.     std::ios_base::sync_with_stdio(false);
  19.     std::cin.tie(0); std::cout.tie(0); std::cerr.tie(0);
  20.  
  21.     int n, root; std::cin >> n >> root; --root;
  22.  
  23.     std::vector<std::vector<Edge>> edges(n);
  24.  
  25.     for (int i = 1; i < n; ++i) {
  26.         int u, v, w; std::cin >> u >> v >> w; --u, --v;
  27.         edges[u].push_back(Edge{v,w});
  28.         edges[v].push_back(Edge{u,w});
  29.     }
  30.  
  31.     std::vector<int> s; // after dfs array s contains xor sums from vertices to root
  32.  
  33.     std::function<void(int,int,int)> visit = [&](const int curr, const int parent, const int sum) {        
  34.         s.push_back(sum);
  35.         for (auto& edge : edges[curr]) {
  36.             if (edge.vertex != parent) {
  37.                 visit(edge.vertex, curr, sum ^ edge.cost);
  38.             }
  39.         }
  40.     };
  41.  
  42.     visit(root, -1, 0); // run dfs for calculating xor sums from vertices to root
  43.  
  44.     std::sort(s.begin()+1, s.end()); // sort array s: now array s is implicit prefix tree
  45.  
  46.     // Calculate answer:
  47.     int answ = 0;
  48.     for (int i = 1; i+1 < n; ++i) {
  49.         // find max s[i] ^ s[j] for j = i+1 to n-1 in O(log(n) * WORD_WIDTH) using implicit prefix tree
  50.         int l = i+1, r = n-1;
  51.         for (int pow = 31; pow >= 0; --pow) {
  52.             // Binary search: s[low][pow] == 0, s[high][pow] == 1
  53.             int low = l-1, high = r+1;
  54.             while (high - low > 1) {
  55.                 int mid = (low + high) / 2;
  56.                 if ((s[mid] >> pow) & 1) {
  57.                     high = mid;
  58.                 } else {
  59.                     low = mid;
  60.                 }
  61.             }
  62.             if (high == l || low == r) {
  63.                 continue;
  64.             }
  65.             if ((s[i] >> pow) & 1) {
  66.                 r = low;   // continue on [l, low]
  67.             } else {
  68.                 l = low+1; // continue on [low+1, r]
  69.             }
  70.         }
  71.         // Update answer:
  72.         answ = std::max(answ, s[l] ^ s[i]);
  73.     }
  74.     std::cout << answ;
  75.     return 0;
  76. }
Success #stdin #stdout 0s 4288KB
comments (?)
stdin
copy 
5 1
2 1 4
2 3 9
1 4 8
1 5 5
stdout
copy 
13
https://ideone.com/ildfd2
language:
C++14 (gcc 8.3)
created:
6 years 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!