Advertisement
Soupborsh

Untitled

Mar 26th, 2025 (edited)
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <utility>
  4. #include <vector>
  5.  
  6. #define ULL unsigned long long
  7. #define LL long long
  8. #define uint unsigned int
  9.  
  10. uint sz_max = 1;
  11.  
  12. typedef struct {
  13.   uint a;
  14.   uint b;
  15.   uint c;
  16. } line;
  17.  
  18. bool comp(line x, line y) { return x.c < y.c; }
  19.  
  20. std::vector<uint> p, sz;
  21.  
  22. // O(log(n))
  23. uint get(uint v) {
  24.   if (v == p[v])
  25.     return v;
  26.   p[v] = get(p[v]);
  27.   return p[v];
  28. }
  29.  
  30. bool check(uint v, uint u) {
  31.   if (get(v) == get(u))
  32.     return true;
  33.   else
  34.     return false;
  35. }
  36.  
  37. bool unite(uint v, uint u) {
  38.   int x = get(v);
  39.   int y = get(u);
  40.   if (x == y)
  41.     return false;
  42.   if (sz[x] > sz[y])
  43.     std::swap(x, y);
  44.   p[x] = y;
  45.   sz[y] += sz[x];
  46.  
  47.   if (sz[y] > sz_max) {
  48.     sz_max = sz[y];
  49.   }
  50.   return true;
  51. }
  52.  
  53. int main() {
  54.   uint n = 0;
  55.   scanf("%u", &n);
  56.  
  57.   p.resize(n, 0);
  58.   sz.resize(n, 0);
  59.  
  60.   uint n_cmp = n;
  61.  
  62.   for (uint i = 0; i < n; i++) {
  63.     p[i] = i;
  64.     sz[i] = 1;
  65.   }
  66.  
  67.   uint m;
  68.   scanf("%u", &m);
  69.  
  70.   std::vector<line> lines(m);
  71.  
  72.   for (uint i = 0; i < m; i++) {
  73.     scanf("%u %u %u", &lines[i].a, &lines[i].b, &lines[i].c);
  74.     lines[i].a--;
  75.     lines[i].b--;
  76.     // if (unite(lines[i].a, lines[i].b)) {
  77.     //   n_cmp--;
  78.     // }
  79.  
  80.     // printf("%u %u\n", n_cmp, sz_max);
  81.   }
  82.  
  83.   ULL total_cost = 0;
  84.  
  85.   std::sort(lines.begin(), lines.end(), comp);
  86.  
  87.   for (line line : lines) {
  88.     if (get(line.a) != get(line.b)) {
  89.       unite(line.a, line.b);
  90.       total_cost += line.c;
  91.       n_cmp--;
  92.     }
  93.   }
  94.  
  95.   if (n_cmp != 1) {
  96.     printf("IMPOSSIBLE");
  97.     return 0;
  98.   }
  99.  
  100.   printf("%llu\n", total_cost);
  101.  
  102.   return 0;
  103. }
  104.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement