oj.uz

답안 #908937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
908937 2024-01-17T02:37:23 Z Sandarach151 Odašiljači (COCI20_odasiljaci) C++17
0 / 70
 81 ms 18880 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){
    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;
    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());
    // for(Edge edge : vect){
    //     cout << edge.node1 << ", " << edge.node2 << ": " << edge.weight << '\n';
    // }
    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", minn);
    return 0;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Incorrect 1 ms 728 KB Output isn't correct
6 Incorrect 15 ms 5604 KB Output isn't correct
7 Incorrect 17 ms 6092 KB Output isn't correct
8 Incorrect 38 ms 18880 KB Output isn't correct
9 Incorrect 76 ms 17348 KB Output isn't correct
10 Incorrect 81 ms 17344 KB Output isn't correct