oj.uz

답안 #906679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
906679 2024-01-14T17:13:57 Z vjudge1 Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 267 ms 27072 KB 
#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 = (long double)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 / (long double)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);
    }

  long double ans = kruskal();
  cout << setprecision(15) << ans;

  return 0;
}

Subtask #1
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 796 KB Output is correct
6 Correct 53 ms 7116 KB Output is correct
7 Correct 54 ms 7624 KB Output is correct
8 Correct 133 ms 27056 KB Output is correct
9 Correct 267 ms 27072 KB Output is correct
10 Correct 263 ms 25280 KB Output is correct