제출 #904064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
904064		vjudge1	Odašiljači (COCI20_odasiljaci)	C++14	0 / 70	177 ms	34508 KiB

odasiljaci

#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(){
	int n;
	cin >> n;
	vector<pii>allNodes;
	vector<pair<long double, pair<int, int>>>nodes;
	for(int i = 0; i < n; i++){
		int 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;
			int lado1 = abs(max(allNodes[i].first, allNodes[j].first)-min(allNodes[i].first, allNodes[j].first));
			int 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;
        int a = nodes[i].second.first;
        int 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(7) << costo_total/2.0 << "\n";

}

컴파일 시 표준 에러 (stderr) 메시지

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++){
      |                    ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 70