#include <bits/stdc++.h>
using namespace std;
struct Dsu {
vector<int> parent, rank, size;
Dsu(int N) {
parent.resize(N);
rank.resize(N);
size.resize(N, 1);
for (int i = 0; i < N; i++){
parent[i] = i;
}
}
bool isSameSet(int i, int j){
return findSet(i) == findSet(j);
}
int findSet(int i) {
if(parent[i] == i){
return i;
}else{
return parent[i] = findSet(parent[i]);
}
}
void unionSet(int i, int j){
int x = findSet(i);
int y = findSet(j);
if (x != y){
if (rank[x] > rank[y]){
parent[y] = x;
size[x] += size[y];
}else if(rank[x] < rank[y]){
parent[x] = y;
size[y] += size[x];
}else{
parent[x] = y;
size[y] += size[x];
rank[y]++;
}
}
}
int getSize(int i){
return size[findSet(i)];
}
};
int main(){
int n;
cin >> n;
pair<long double, long double> ubicaciones[n];
long double x,y;
for (int i = 0; i<n; i++){
cin >> x >> y;
ubicaciones[i].first = x;
ubicaciones[i].second = y;
}
vector<pair<double,pair<int,int>>> edges;
for (int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(i == j) continue;
double distancia = sqrt((ubicaciones[i].first-ubicaciones[j].first) * (ubicaciones[i].first-ubicaciones[j].first) + (ubicaciones[i].second-ubicaciones[j].second)*(ubicaciones[i].second-ubicaciones[j].second));
edges.push_back({distancia,{i,j}});
}
}
sort(edges.begin(), edges.end());
Dsu dsu(n);
// Kruskal
long double costo_total = 0;
for(int i = 0; i < n; i++){
double w = edges[i].first;
int a = edges[i].second.first;
int b = edges[i].second.second;
if(!dsu.isSameSet(a, b)){ // Si a y b no estan en la misma componente conexa
dsu.unionSet(a, b); // entonces las uno
costo_total = w;
}
}
costo_total /= 2;
cout << fixed<< setprecision(7)<< costo_total << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
360 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
612 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
616 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
740 KB |
Output isn't correct |
| 6 |
Incorrect |
32 ms |
5848 KB |
Output isn't correct |
| 7 |
Incorrect |
33 ms |
6360 KB |
Output isn't correct |
| 8 |
Incorrect |
79 ms |
17876 KB |
Output isn't correct |
| 9 |
Incorrect |
121 ms |
18728 KB |
Output isn't correct |
| 10 |
Incorrect |
119 ms |
18880 KB |
Output isn't correct |
