Submission #908948

#	Time	Username	Problem	Language	Result	Execution time	Memory
908948		Sandarach151	Odašiljači (COCI20_odasiljaci)	C++17	0 / 70	78 ms	17604 KiB

odasiljaci

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

vector<int> link, sze;

struct Edge{
    int node1;
    int node2;
    long double weight;

    Edge(int a, int b, long double c){
        node1=a;
        node2=b;
        weight=c;
    }
};

bool operator<(const Edge& a, const Edge& b){
    return a.weight<b.weight;
}

int find(int x){
    while(x!=link[x]) x = link[x];
    return x;
}

bool same(int a, int b){
    return find(a)==find(b);
}

void unite(int a, int b){
    if(sze[a]<sze[b]) swap(a, b);
    link[b]=a;
    sze[a]+=sze[b];
}

int main(){
    int n;
    cin >> n;
    pair<long double, long double> arr[n];
    for(int i=0; i<n; i++){
        cin >> arr[i].first >> arr[i].second;
    }
    link.assign(n, 0);
    sze.assign(n, 1);
    for(int i=0; i<n; i++){
        link[i]=i;
        sze[i]=1;
    }
    vector<Edge> vect;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            Edge temp(i, j, sqrt(pow(arr[i].first-arr[j].first, 2)+pow(arr[i].second-arr[j].second, 2))/2);
            vect.push_back(temp);
        }
    }
    sort(vect.begin(), vect.end());
    int cnt = 0;
    long double minn = 0;
    for(int pos = 0; pos<vect.size() && cnt<n-1; pos++){
        if(!same(vect[pos].node1, vect[pos].node2)){
            unite(vect[pos].node1, vect[pos].node2);
            minn = vect[pos].weight;
            cnt++;
        }
    }
    printf("%.10Lf\n", minn);
    return 0;
}

Compilation message (stderr)

odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:60:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int pos = 0; pos<vect.size() && cnt<n-1; pos++){
      |                      ~~~^~~~~~~~~~~~

• Subtask 1: 0 / 70