fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. const int MAXN = 1e5 + 15;
  6.  
  7. int N;
  8.  
  9. struct DATA {
  10.     int x, y, z, id;
  11. };
  12.  
  13. struct cmp {
  14.     bool operator() (DATA a, DATA b) {
  15.         return a.x < b.x;
  16.     }
  17. };
  18.  
  19. struct cmp1 {
  20.     bool operator() (DATA a, DATA b) {
  21.         return a.y < b.y;
  22.     }
  23. };
  24.  
  25. struct cmp2 {
  26.     bool operator() (DATA a, DATA b) {
  27.         return a.z < b.z;
  28.     }
  29. };
  30.  
  31. struct Edge {
  32.     int u, v, w;
  33. };
  34.  
  35. struct cmpe {
  36.     bool operator() (Edge x, Edge y) {
  37.         return x.w < y.w;
  38.     }
  39. };
  40.  
  41. struct Dosu {
  42.     int par[MAXN], sz[MAXN];
  43.  
  44.     void INIT() {
  45.         for (int i = 1; i <= N; i++) {
  46.             par[i] = i;
  47.             sz[i] = 1;
  48.         }
  49.     }
  50.  
  51.     int find_set(int u) {
  52.         return (par[u] == u ? u : par[u] = find_set(par[u]));
  53.     }
  54.  
  55.     void union_set(int u, int v) {
  56.         u = find_set(u), v = find_set(v);
  57.         if (u == v) return;
  58.         if (sz[u] < sz[v]) swap(u, v);
  59.         par[v] = par[u];
  60.         sz[u] += sz[v];
  61.     }
  62.  
  63. } DSU;
  64.  
  65. DATA A[MAXN];
  66. vector<Edge> v;
  67.  
  68. void upd() {
  69.     for (int i = 2; i <= N; i++) {
  70.         int a = abs(A[i].x - A[i - 1].x);
  71.         int b = abs(A[i].y - A[i - 1].y);
  72.         int c = abs(A[i].z - A[i - 1].z);
  73.         int tmp = min({a, b, c});
  74.         v.push_back({A[i].id, A[i - 1].id, tmp});
  75.     }
  76. }
  77.  
  78.  
  79.  
  80. main() {
  81.     ios_base::sync_with_stdio(0);
  82.     cin.tie(0);
  83.     cout.tie(0);
  84.  
  85.     cin >> N;
  86.     for (int i = 1; i <= N; ++i) {
  87.         cin >> A[i].x >> A[i].y >> A[i].z;
  88.         A[i].id = i;
  89.     }
  90.  
  91.     sort (A + 1, A + N + 1, cmp());
  92.     upd();
  93.     sort (A + 1, A + N + 1, cmp1());
  94.     upd();
  95.     sort (A + 1, A + N + 1, cmp2());
  96.     upd();
  97.     sort(v.begin(), v.end(), cmpe());
  98.     int MST = 0;
  99.     DSU.INIT();
  100.     for (auto E : v) {
  101.         if (DSU.find_set(E.u) == DSU.find_set(E.v)) continue;
  102.         DSU.union_set(E.u, E.v);
  103.         MST += E.w;
  104.     }
  105.  
  106.     cout << MST;
  107. }
  108.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XrhrWy
language:
C++ (gcc 8.3)
created:
29 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!