fork download 
  1. /*
  2. Problem: Finding best charging station location in a tree
  3.  
  4. You have a tree with n nodes (cities) rooted at node 1.
  5. Each edge has a weight (distance).
  6.  
  7. For each query, you're given:
  8. - u, v: two cities that need to receive deliveries
  9. - c: total fuel capacity
  10.  
  11. You need to choose a starting city 's' where:
  12. - Cars go from s down to u (delivery 1)
  13. - Cars go from s down to v (delivery 2)  
  14. - Cars go from s up to root (return to headquarters)
  15. - Total distance traveled <= c (fuel capacity)
  16.  
  17. Goal: Among all valid starting cities, maximize the fuel used.
  18. If no valid starting city exists, output 0.
  19.  
  20. ==================================================================================
  21. HOW WE SOLVE THIS:
  22. ==================================================================================
  23.  
  24. OBSERVATION 1: Where can we start from?
  25. The starting city 's' must be able to reach both u and v by going downwards.
  26. This means s must be an ANCESTOR of both u and v.
  27. In other words, s must be somewhere on the path from root to both u and v.
  28.  
  29. The deepest common ancestor of u and v is their LCA (Lowest Common Ancestor).
  30. So s can be any node from root to LCA(u,v).
  31.  
  32. OBSERVATION 2: How do we calculate distances?
  33. Let dist[x] = distance from root to node x (sum of edge weights on path)
  34.  
  35. For any ancestor s of both u and v:
  36. - Distance from s to u = dist[u] - dist[s] (going down)
  37. - Distance from s to v = dist[v] - dist[s] (going down)
  38. - Distance from s to root = dist[s] (going up)
  39.  
  40. Total fuel used = (dist[u] - dist[s]) + (dist[v] - dist[s]) + dist[s]
  41.                 = dist[u] + dist[v] - dist[s]
  42.  
  43. OBSERVATION 3: What's the constraint?
  44. We need: dist[u] + dist[v] - dist[s] <= c
  45. Rearranging: dist[s] >= dist[u] + dist[v] - c
  46.  
  47. Let's call (dist[u] + dist[v] - c) the "minimum_distance"
  48. We need: dist[s] >= minimum_distance
  49.  
  50. OBSERVATION 4: How do we maximize fuel used?
  51. Fuel used = dist[u] + dist[v] - dist[s]
  52.  
  53. Since dist[u] and dist[v] are fixed, to maximize this we need to MINIMIZE dist[s].
  54.  
  55. So we want the SMALLEST dist[s] that still satisfies dist[s] >= minimum_distance.
  56.  
  57. STRATEGY:
  58. 1. Find LCA of u and v (call it L)
  59. 2. Calculate minimum_distance = dist[u] + dist[v] - c
  60. 3. If minimum_distance > dist[L], no valid s exists → output 0
  61. 4. Otherwise, find the highest ancestor of L with dist >= minimum_distance
  62. 5. This gives us the s with smallest valid dist[s], maximizing fuel used
  63.  
  64. IMPLEMENTATION DETAILS:
  65. - Use binary lifting to quickly find LCA
  66. - Use binary lifting to jump to the right ancestor
  67. - Precompute distances from root using DFS
  68. - Use __int128 to avoid overflow when adding large distances
  69.  
  70. Example:
  71. Tree:      1 (root)
  72.           / \
  73.          2   3
  74.         /
  75.        4
  76.  
  77. dist[1]=0, dist[2]=5, dist[3]=8, dist[4]=12
  78.  
  79. Query: u=4, v=3, c=20
  80. - LCA(4,3) = 1
  81. - minimum_distance = 12 + 8 - 20 = 0
  82. - Find highest ancestor of 1 with dist >= 0 → that's 1 itself
  83. - Answer = 12 + 8 - 0 = 20 ✓
  84.  
  85. Time complexity: O(n log n) preprocessing + O(log n) per query
  86. Space complexity: O(n log n) for binary lifting table
  87. ==================================================================================
  88. */
  89.  
  90. #include <bits/stdc++.h>
  91. using namespace std;
  92.  
  93. int main(){
  94.     ios::sync_with_stdio(false);
  95.     cin.tie(nullptr);
  96.  
  97.     int num_cities, num_queries;
  98.     cin >> num_cities >> num_queries;
  99.  
  100.     // Build the tree as an adjacency list
  101.     // graph[city] = list of {neighbor, edge_weight}
  102.     vector<vector<pair<int, long long>>> graph(num_cities + 1);
  103.  
  104.     for(int i = 0; i < num_cities - 1; i++){
  105.         int city_a, city_b;
  106.         long long road_length;
  107.         cin >> city_a >> city_b >> road_length;
  108.  
  109.         graph[city_a].push_back({city_b, road_length});
  110.         graph[city_b].push_back({city_a, road_length});
  111.     }
  112.  
  113.     // Prepare for binary lifting (jumping up the tree quickly)
  114.     // We need log2(n) levels of jumps
  115.     int max_jumps = 1;
  116.     while((1 << max_jumps) <= num_cities) {
  117.         max_jumps++;
  118.     }
  119.  
  120.     // ancestor[jump_size][city] = where you end up if you jump 2^jump_size steps up from city
  121.     vector<vector<int>> ancestor(max_jumps, vector<int>(num_cities + 1, 0));
  122.  
  123.     // Basic info about each city
  124.     vector<int> level(num_cities + 1, 0);  // how deep in the tree (root is 0)
  125.     vector<long long> distance_from_root(num_cities + 1, 0);  // total distance from root
  126.  
  127.     // Build the tree structure using DFS from root (city 1)
  128.     vector<int> parent_of(num_cities + 1, 0);
  129.     vector<int> dfs_stack;
  130.     dfs_stack.reserve(num_cities);
  131.     dfs_stack.push_back(1);
  132.  
  133.     parent_of[1] = 0;  // root has no parent
  134.     level[1] = 0;
  135.     distance_from_root[1] = 0;
  136.  
  137.     while(!dfs_stack.empty()){
  138.         int city = dfs_stack.back();
  139.         dfs_stack.pop_back();
  140.  
  141.         // Set up first level of binary lifting (jump 1 step = go to parent)
  142.         ancestor[0][city] = parent_of[city];
  143.  
  144.         // Visit all neighbors
  145.         for(auto [neighbor, road_length] : graph[city]){
  146.             // Don't go back to parent
  147.             if(neighbor == parent_of[city]) continue;
  148.  
  149.             parent_of[neighbor] = city;
  150.             level[neighbor] = level[city] + 1;
  151.             distance_from_root[neighbor] = distance_from_root[city] + road_length;
  152.             dfs_stack.push_back(neighbor);
  153.         }
  154.     }
  155.  
  156.     // Build the rest of the binary lifting table
  157.     // Jump 2^j steps = jump 2^(j-1) steps twice
  158.     for(int jump_size = 1; jump_size < max_jumps; jump_size++){
  159.         for(int city = 1; city <= num_cities; city++){
  160.             int halfway = ancestor[jump_size - 1][city];
  161.             if(halfway != 0) {
  162.                 ancestor[jump_size][city] = ancestor[jump_size - 1][halfway];
  163.             } else {
  164.                 ancestor[jump_size][city] = 0;
  165.             }
  166.         }
  167.     }
  168.  
  169.     // Function: find the lowest common ancestor of two cities
  170.     auto find_lca = [&](int city_a, int city_b) {
  171.         // Make sure city_a is deeper (or same depth)
  172.         if(level[city_a] < level[city_b]) {
  173.             swap(city_a, city_b);
  174.         }
  175.  
  176.         // Bring city_a up to the same level as city_b
  177.         int level_difference = level[city_a] - level[city_b];
  178.         for(int jump = 0; jump < max_jumps; jump++){
  179.             if(level_difference & (1 << jump)) {
  180.                 city_a = ancestor[jump][city_a];
  181.             }
  182.         }
  183.  
  184.         // If they're the same now, we found the LCA
  185.         if(city_a == city_b) return city_a;
  186.  
  187.         // Otherwise, jump both up until their parents are the same
  188.         for(int jump = max_jumps - 1; jump >= 0; jump--){
  189.             if(ancestor[jump][city_a] != ancestor[jump][city_b]){
  190.                 city_a = ancestor[jump][city_a];
  191.                 city_b = ancestor[jump][city_b];
  192.             }
  193.         }
  194.  
  195.         // Now their parent is the LCA
  196.         return ancestor[0][city_a];
  197.     };
  198.  
  199.     // Function: find the highest ancestor with distance >= threshold
  200.     // (closest to root while still satisfying the constraint)
  201.     auto find_highest_valid_ancestor = [&](int city, __int128 min_distance) {
  202.         int current = city;
  203.  
  204.         // Try jumping up as far as possible while staying valid
  205.         for(int jump = max_jumps - 1; jump >= 0; jump--){
  206.             int parent = ancestor[jump][current];
  207.  
  208.             // Can we jump this far and still be valid?
  209.             if(parent != 0 && (__int128)distance_from_root[parent] >= min_distance) {
  210.                 current = parent;
  211.             }
  212.         }
  213.  
  214.         return current;
  215.     };
  216.  
  217.     // Process each query
  218.     while(num_queries--){
  219.         int delivery_1, delivery_2;
  220.         long long fuel_capacity;
  221.         cin >> delivery_1 >> delivery_2 >> fuel_capacity;
  222.  
  223.         // Find the deepest possible starting point (LCA)
  224.         int lowest_common = find_lca(delivery_1, delivery_2);
  225.  
  226.         // Calculate the minimum distance our starting point must have from root
  227.         // Use __int128 to prevent overflow when adding large distances
  228.         __int128 sum_distances = (__int128)distance_from_root[delivery_1] + 
  229.                                   (__int128)distance_from_root[delivery_2];
  230.         __int128 min_distance = sum_distances - (__int128)fuel_capacity;
  231.  
  232.         // If even the deepest valid point (LCA) doesn't have enough distance, no solution
  233.         if(min_distance > (__int128)distance_from_root[lowest_common]){
  234.             cout << 0 << "\n";
  235.             continue;
  236.         }
  237.  
  238.         // If we can start from root itself, do that (uses most fuel)
  239.         if(min_distance <= 0){
  240.             // Check if total distance fits in capacity
  241.             if(sum_distances <= (__int128)fuel_capacity) {
  242.                 // Safe to convert back to long long since it fits in capacity
  243.                 cout << (long long)sum_distances << "\n";
  244.             } else {
  245.                 cout << 0 << "\n";
  246.             }
  247.             continue;
  248.         }
  249.  
  250.         // Find the best starting city (highest ancestor with valid distance)
  251.         int start_city = find_highest_valid_ancestor(lowest_common, min_distance);
  252.  
  253.         // Calculate how much fuel we'd use
  254.         // Use __int128 to prevent overflow
  255.         __int128 fuel_used = sum_distances - (__int128)distance_from_root[start_city];
  256.  
  257.         // Make sure we don't exceed capacity (should always be true, but be safe)
  258.         if(fuel_used <= (__int128)fuel_capacity) {
  259.             cout << (long long)fuel_used << "\n";
  260.         } else {
  261.             cout << 0 << "\n";
  262.         }
  263.     }
  264.  
  265.     return 0;
  266. }
Runtime error #stdin #stdout #stderr 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/8tyLbq
language:
C++14 (gcc 8.3)
created:
79 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!