#include <bits/stdc++.h>
using namespace std;
#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 loop(i, a, b) for(int i = a; i < b; i++)
#define ff first
#define ss second
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vpii = vector<pair<int, int>>;
using vvpii = vector<vector<pair<int, int>>>;
using vb = vector<bool>;
const int MOD = (int)1e9 + 7;
const int maxN = 2e5;
const int INF = INT_MAX;
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(){
ll n;
cin >> n;
vector<pii>allNodes;
vector<pair<long double, pair<int, int>>>nodes;
for(int i = 0; i < n; i++){
ll a, b;
cin >> a >> b;
allNodes.pb({a, b});
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) continue;
ll lado1 = abs(max(allNodes[i].first, allNodes[j].first)-min(allNodes[i].first, allNodes[j].first));
ll lado2 = abs(max(allNodes[j].second, allNodes[i].second)-min(allNodes[j].second, allNodes[i].first));
long double w = sqrt(((lado1)*(lado1))+((lado2)*(lado2)));
nodes.pb({w, {i, j}});
}
}
sort(all(nodes));
Dsu dsu(n);
long double costo_total = 0;
for(int i = 0; i < nodes.size(); i++){
long double w = nodes[i].first;
ll a = nodes[i].second.first;
ll b = nodes[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;
}
}
// Finalmente se obtiene el costo minimo para conectar todos los nodos
cout << fixed << setprecision(9) << costo_total/2.0 << "\n";
}
Compilation message
odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i = 0; i < nodes.size(); i++){
| ~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
360 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
740 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
996 KB |
Output isn't correct |
| 6 |
Incorrect |
47 ms |
9428 KB |
Output isn't correct |
| 7 |
Incorrect |
48 ms |
10448 KB |
Output isn't correct |
| 8 |
Incorrect |
112 ms |
35260 KB |
Output isn't correct |
| 9 |
Incorrect |
182 ms |
34248 KB |
Output isn't correct |
| 10 |
Incorrect |
182 ms |
34468 KB |
Output isn't correct |
