fork download
  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
stdin
5 1
2 1 4
2 3 9
1 4 8
1 5 5
stdout
13