fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. // Số lượng nút tối đa: N ban đầu + M nút mới (nội bộ) <= 400005
  9. const int MAX_NODES = 400005;
  10. const int LOG_MAX = 20; 
  11.  
  12. // ------------------- DSU (Union-Find) -------------------
  13. int parent_dsu[MAX_NODES]; 
  14. int find_set(int v) {
  15.     if (v == parent_dsu[v])
  16.         return v;
  17.     return parent_dsu[v] = find_set(parent_dsu[v]);
  18. }
  19.  
  20. // ------------------- Cây Kruskal và Binary Lifting -------------------
  21. int current_node;           
  22. int up[MAX_NODES][LOG_MAX];     
  23. long long node_cost[MAX_NODES]; 
  24. int depth[MAX_NODES];           
  25.  
  26. void init(int n) {
  27.     for (int i = 1; i <= n; ++i) {
  28.         parent_dsu[i] = i; 
  29.         depth[i] = 0;      
  30.         up[i][0] = 0;      
  31.         node_cost[i] = 0; 
  32.     }
  33.     // Khởi tạo các nút có thể được tạo ra
  34.     for (int i = n + 1; i < MAX_NODES; ++i) {
  35.         up[i][0] = 0;
  36.         depth[i] = 0;
  37.     }
  38.     current_node = n;
  39. }
  40.  
  41. void union_sets(int u, int v, long long w) {
  42.     int root_u = find_set(u);
  43.     int root_v = find_set(v);
  44.  
  45.     if (root_u != root_v) {
  46.         current_node++;
  47.         int new_root = current_node;
  48.  
  49.         // 1. DSU: Hợp nhất
  50.         parent_dsu[root_u] = new_root;
  51.         parent_dsu[root_v] = new_root;
  52.         parent_dsu[new_root] = new_root;
  53.  
  54.         // 2. Cây Kruskal: Trọng số và Độ sâu
  55.         node_cost[new_root] = w; 
  56.         depth[new_root] = max(depth[root_u], depth[root_v]) + 1;
  57.  
  58.         // 3. Binary Lifting: Cập nhật nút cha
  59.         up[root_u][0] = new_root;
  60.         up[root_v][0] = new_root;
  61.  
  62.         // Tiền xử lý các bước nhảy lớn hơn cho nút mới
  63.         for (int k = 1; k < LOG_MAX; ++k) {
  64.             up[new_root][k] = up[up[new_root][k - 1]][k - 1];
  65.         }
  66.     }
  67. }
  68.  
  69. // Hàm tìm LCA
  70. int find_lca(int u, int v) {
  71.     // 1. Đảm bảo u là nút sâu hơn
  72.     if (depth[u] < depth[v]) swap(u, v);
  73.  
  74.     // 2. Đưa u lên cùng độ sâu với v
  75.     for (int k = LOG_MAX - 1; k >= 0; --k) {
  76.         if (up[u][k] != 0 && depth[u] - (1 << k) >= depth[v]) {
  77.             u = up[u][k];
  78.         }
  79.     }
  80.  
  81.     if (u == v) return u; 
  82.  
  83.     // 3. Nhảy lên từ u và v đồng thời
  84.     for (int k = LOG_MAX - 1; k >= 0; --k) {
  85.         // Chỉ nhảy nếu nút cha khác nhau VÀ không phải nút 0 (null)
  86.         if (up[u][k] != up[v][k] && up[u][k] != 0) {
  87.             u = up[u][k];
  88.             v = up[v][k];
  89.         }
  90.     }
  91.  
  92.     // 4. LCA là nút cha (tổ tiên 2^0) của u (hoặc v) hiện tại
  93.     return up[u][0];
  94. }
  95.  
  96. long long query_min_max_cost(int s, int t) {
  97.     // 1. Kiểm tra tính liên thông: Nếu gốc DSU khác nhau, chưa thể đi
  98.     if (find_set(s) != find_set(t)) {
  99.         return -1;
  100.     }
  101.  
  102.     // 2. Kiểm tra trường hợp đặc biệt: Nếu s và t đã được kết nối 
  103.     // nhưng chưa có nút nội bộ nào được tạo ra (tức là chỉ có các nút lá)
  104.     // Trường hợp này không nên xảy ra nếu find_set(s) == find_set(t)
  105.     // và thuật toán đã chạy đúng.
  106.  
  107.     // 3. Tìm LCA
  108.     int lca = find_lca(s, t);
  109.  
  110.     // 4. Kết quả là giá trị tại nút LCA
  111.     // Nếu LCA là 0 (điều kiện này chỉ xảy ra nếu s và t không liên thông hoặc 
  112.     // lca là nút lá, nhưng lca phải là nút nội bộ nếu s != t và đã liên thông)
  113.     if (lca == 0) return -1; // Fallback an toàn, mặc dù về mặt lý thuyết lca > n.
  114.  
  115.     return node_cost[lca];
  116. }
  117.  
  118. int main() {
  119.     ios_base::sync_with_stdio(false);
  120.     cin.tie(NULL);
  121.  
  122.     int n, m;
  123.     if (!(cin >> n >> m)) return 0;
  124.  
  125.     init(n);
  126.  
  127.     for (int i = 0; i < m; ++i) {
  128.         int u, v, s, t;
  129.         long long w;
  130.         if (!(cin >> u >> v >> w >> s >> t)) break;
  131.  
  132.         // 1. Thêm cạnh 
  133.         union_sets(u, v, w);
  134.  
  135.         // 2. Truy vấn
  136.         cout << query_min_max_cost(s, t) << "\n";
  137.     }
  138.  
  139.     return 0;
  140. }
Success #stdin #stdout 0.01s 38808KB
comments (?)
stdin
copy 
6 8
1 2 4 1 4
1 4 5 2 4
2 5 7 4 5
3 5 6 4 3
4 5 1 2 5
3 6 3 4 6
5 6 2 2 6
1 5 4 2 3
stdout
copy 
-1
5
7
7
5
7
5
5
https://ideone.com/yen4Yr
language:
C++14 (gcc 8.3)
created:
8 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!