oj.uz

Submission #908956

# Submission time Handle Problem Language Result Execution time Memory
908956 2024-01-17T03:26:16 Z Sandarach151 Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 80 ms 18372 KB 
#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){
  	a = find(a);
  b = find(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

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

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 728 KB Output is correct
6 Correct 15 ms 6600 KB Output is correct
7 Correct 17 ms 6344 KB Output is correct
8 Correct 39 ms 18112 KB Output is correct
9 Correct 80 ms 17860 KB Output is correct
10 Correct 78 ms 18372 KB Output is correct