제출 #906678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
906678		vjudge1	Odašiljači (COCI20_odasiljaci)	C++17	35 / 70	268 ms	26528 KiB

odasiljaci

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

#define fastIO()                     \
  ios_base::sync_with_stdio(false);  \
  cin.tie(NULL);                     \
  cout.tie(NULL);
#define endl '\n'
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define allr(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vb = vector<bool>;
using vi = vector<int>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvi = vector<vector<int>>;
using vvpii = vector<vector<pair<int, int>>>;
const int MOD = (int)1e9 + 7;

struct Edge{
  long double w;
  ll a1, b1, a2, b2;

  bool operator<(const Edge & o) {
    return w < o.w;
  }

  void calculate_dist(){
    w = (abs(a1-b1)*abs(a1-b1)) + (abs(a2-b2)*abs(a2-b2));
    w = sqrt(w);
  }
};

int n;  
vector<pll> node;
vector<Edge> adj;

struct DSU {
  map<pll, pll> p;
  map<pll, ll> rank;

  DSU() {
    for (int i=0; i < n; i++) {
      p.insert({node[i], node[i]});
      rank.insert({node[i], 1});
    }
  }

  pll find(pll v) {
    return ( v == p[v]) ? v : p[v] = find(p[v]);
  }

  void unite(pll a, pll b) {
    a = find(a);
    b = find(b);

    if (a == b) return;

    if (rank[a] < rank[b]) swap(a, b);
    p[b] = a;
    if (rank[a] == rank[b]) rank[a]++;
  }
};

long double kruskal() {
  sort(all(adj));
  long double max_edge = adj[0].w;
  DSU dsu;

  for (auto[w,a1,b1,a2,b2] : adj) {
    if (dsu.find({a1, a2}) == dsu.find({b1, b2}))
      continue;
    dsu.unite({a1, a2} , {b1, b2});
    max_edge = max(max_edge, w);
  }

  return max_edge / 2;
}


int main() {
  fastIO();

  ll x, y;

  cin >> n;
  
  node.resize(n);
  for (int i=0; i < n; i++) {
    cin >> x >> y;
    node[i] = {x, y};
  }

  for (int i=0; i < n; i++)
    for (int j=i+1; j < n; j++) {
      Edge e = {0, node[i].ff, node[j].ff, node[i].ss, node[j].ss};
      e.calculate_dist();
      adj.pb(e);
    }

  cout << kruskal();

  return 0;
}

• Subtask 1: 35 / 70