oj.uz

Submission #498780

# Submission time Handle Problem Language Result Execution time Memory
498780 2021-12-26T10:35:55 Z Karabasan Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 217 ms 49300 KB 
#include <bits/stdc++.h>
#define ll long long
#define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define int long long
#define double long double
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,avx")
#pragma GCC optimize("unroll-loops")

int n;
vector<pair<double,int> > v[1005];
pair<int,int> p[1005];
int vis[1005];
double mx;
void solve()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>p[i].first>>p[i].second;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            v[i].push_back({-sqrt(abs(p[i].first-p[j].first)*abs(p[i].first-p[j].first)+abs(p[i].second-p[j].second)*abs(p[i].second-p[j].second))/2.0,j});
            v[j].push_back({-sqrt(abs(p[i].first-p[j].first)*abs(p[i].first-p[j].first)+abs(p[i].second-p[j].second)*abs(p[i].second-p[j].second))/2.0,i});
        }
    }
    priority_queue<pair<double,int> > pq;
    pq.push({0,0});
    while(!pq.empty())
    {
        double yol=pq.top().first;
        int x=pq.top().second;
        pq.pop();
        if(vis[x]==1)
            continue;
        vis[x]=1;
        mx=min(mx,yol);
        for(int i=0;i<v[x].size();i++)
        {
            if(vis[v[x][i].second])
                continue;
            pq.push({v[x][i].first,v[x][i].second});
        }
    }
    cout<<setprecision(9)<<-mx<<endl;
}
signed main()
{
    //freopen ("lca.gir","r",stdin);
    //freopen ("lca.cik","w",stdout);
    //fast1
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

Compilation message

odasiljaci.cpp: In function 'void solve()':
odasiljaci.cpp:41:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i=0;i<v[x].size();i++)
      |                     ~^~~~~~~~~~~~

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 47 ms 12732 KB Output is correct
7 Correct 46 ms 12744 KB Output is correct
8 Correct 118 ms 39132 KB Output is correct
9 Correct 215 ms 49196 KB Output is correct
10 Correct 217 ms 49300 KB Output is correct