oj.uz

Submission #485375

# Submission time Handle Problem Language Result Execution time Memory
485375 2021-11-07T12:39:33 Z alexdumitru Odašiljači (COCI20_odasiljaci) C++14
42 / 70
 467 ms 3512 KB 
#include <bits/stdc++.h>
#define a first
#define b second
using namespace std;
int i,n,j,nr,viz[1005];
double rez,delta=0.000000001;
pair<int, int> v[1005];
vector<vector<int> > g;
void dfs(int nod=1)
{
    nr++;
    viz[nod]=1;
    for(int i=0;i<g[nod].size();i++)
        if(!viz[g[nod][i]])
            dfs(g[nod][i]);
}
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i].a>>v[i].b;
    double st=0,dr=1000000000;
    while(dr-st>delta)
    {
        double m=(st+dr)/2;
        nr=0;
        g.clear();
        for(i=1;i<=n+1;i++)
        {
            viz[i]=0;
            g.push_back({});
        }
        for(i=1;i<=n;i++)
            for(j=i+1;j<=n;j++)
            {
                if(sqrt((v[i].a-v[j].a)*(v[i].a-v[j].a)+(v[i].b-v[j].b)*(v[i].b-v[j].b))<=m*2)
                {
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
        dfs();
        if(nr==n)
        {
            rez=m;
            dr=m;
        }
        else st=m;

    }
    cout<<fixed<<setprecision(8)<<rez;
    return 0;
}

Compilation message

odasiljaci.cpp: In function 'void dfs(int)':
odasiljaci.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<g[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~

Subtask #1
42.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Incorrect 3 ms 332 KB Output isn't correct
5 Incorrect 5 ms 340 KB Output isn't correct
6 Correct 76 ms 1396 KB Output is correct
7 Correct 83 ms 1396 KB Output is correct
8 Correct 164 ms 3512 KB Output is correct
9 Incorrect 443 ms 3176 KB Output isn't correct
10 Incorrect 467 ms 3272 KB Output isn't correct