Submission #1318027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318027		hasan	Odašiljači (COCI20_odasiljaci)	C++20	70 / 70	34 ms	34664 KiB

odasiljaci

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

#define endl '\n'
#define dl double
#define int long long
#define ul uint_fast32_t
#define ll int_fast64_t
#define dll long double
#define ull uint_fast64_t
#define spektar this_thread::sleep_for(chrono::milliseconds(50))

const int MAX1=1e3+5;
vector<vector<pair<dll,int>>> k(MAX1);
vector<int> vis(MAX1);
vector<dll> dis(MAX1,2e18);
priority_queue<pair<dll,int>,vector<pair<dll,int>>,greater<pair<dll,int>>> q;

void solve(){
    int n;
    cin >> n;
    vector<array<dll,2>> kk(n);
    for(auto& [a,b]:kk) cin >> a >> b;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            k[i+1].push_back({(dll)sqrt(abs(kk[i][0]-kk[j][0])*abs(kk[i][0]-kk[j][0])+abs(kk[i][1]-kk[j][1])*abs(kk[i][1]-kk[j][1]))/2,j+1});
        }
        //sort(k[i+1].begin(),k[i+1].end());
    }
    q.push({0,1});
    dis[1]=0;
    while(q.size()){
        dll a=q.top().first;
        int b=q.top().second;
        q.pop();
        if(vis[b]) continue;
        vis[b]=1;
        for(auto& [c,d]:k[b]){
            if(max(a,c)<dis[d]){
                dis[d]=max(a,c);
                q.push({dis[d],d});
            }
        }
    }
    dll max1=0;
    for(int i=1; i<=n; i++){
        max1=max(max1,dis[i]);
    }
    cout << fixed << setprecision(8) << max1 << endl;
}

signed main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t=1;
    //cin >> t;
    while(t--){
        solve();
    }
}

• Subtask 1: 70 / 70