Submission #1985184

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long int;

const int MAX_N = (int)1e5 + 5;
const ll MOD = (ll)1e9 + 7;

struct index_point {ll index, x, y;};
struct edge {ll u, v, cost;};

int n;
vector<index_point> ips;

bool comp(const edge &e1, const edge &e2) {
  return e1.cost < e2.cost;
}

vector<edge> es;
ll vsize, esize;

/////////////////////////////////////////////////////////
ll uf_par[MAX_N];
ll uf_rank[MAX_N];

void uf_init(ll n) {
  for (ll i = 0; i < n; ++i) {
    uf_par[i] = i;
    uf_rank[i] = 0;
  }
}

ll uf_find (ll x) {
  if (uf_par[x] == x) {return x;}
  else {
    return uf_par[x] = uf_find(uf_par[x]);
  }
}

void uf_unite(ll x, ll y) {
  x = uf_find(x);
  y = uf_find(y);

  if (x == y) {return;}
  if (uf_rank[x] < uf_rank[y]) {uf_par[x] = y;}
  else {
    uf_par[y] = x;
    if (uf_rank[x] == uf_rank[y]) uf_rank[x] += 1;
  }
}

bool uf_same(ll x, ll y) {
  return uf_find(x) == uf_find(y);
}
/////////////////////////////////////////////////////////

int main(void){
  // Here your code !
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    ll x, y;
    index_point ip;
    scanf("%lld", &x);
    scanf("%lld", &y);
    ip.index = i;
    ip.x = x;
    ip.y = y;
    ips.push_back(ip);
  }

  sort(ips.begin(), ips.end(), [](const index_point a, const index_point b) {return a.x < b.x;}); // sort by x
  for (int i = 1; i < ips.size(); ++i) {
    edge e;
    e.u = ips[i - 1].index;
    e.v = ips[i].index;
    e.cost = ips[i].x - ips[i - 1].x;
    es.push_back(e);
  }

  sort(ips.begin(), ips.end(), [](const index_point a, const index_point b) {return a.y < b.y;}); // sort by x
  for (int i = 1; i < ips.size(); ++i) {
    edge e;
    e.u = ips[i - 1].index;
    e.v = ips[i].index;
    e.cost = ips[i].y - ips[i - 1].y;
    es.push_back(e);
  }

  vsize = n;
  esize = es.size();

  sort(es.begin(), es.end(), comp);
  uf_init(vsize);

  ll res = 0;
  for (int i = 0; i < esize; ++i) {
    edge e = es[i];
    if (!uf_same(e.u, e.v)) {
      uf_unite(e.u, e.v);
      res += e.cost;
    }
  }

  printf("%lld\n", res);

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:59:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:63:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &x);
                      ^
./Main.cpp:64:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &y);
                      ^

Judge Result