Submission #439936

#	Time	Username	Problem	Language	Result	Execution time	Memory
439936		VladM	Circle selection (APIO18_circle_selection)	C++14	7 / 100	265 ms	216932 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

#define DIM 5007

struct circle
{
    long long R, it;
};

long long n, x[DIM], y[DIM], r[DIM], R, it, vis[DIM], par[DIM];

vector<long long> vec[DIM];

vector<circle> c;

bool cmp(circle a, circle b)
{
    if(a.R==b.R) return a.it>b.it;
    return a.R<b.R;
}

int main()
{
    scanf("%lld", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld%lld%lld", &x[i], &y[i], &r[i]);
    }
    for(int i=1; i<=n; i++)
    {
        c.push_back({r[i], i});
        for(int j=1; j<=n; j++)
        {
            if((r[i]+r[j])*(r[i]+r[j])>=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))
            {
                vec[i].push_back(j);
            }
        }
    }
    sort(c.begin(), c.end(), cmp);
    reverse(c.begin(), c.end());
    for(int i=0; i<n; i++)
    {
        R=c[i].R;
        it=c[i].it;
        if(vis[it]!=0) continue;
        vis[it]=1;
        par[it]=it;
        for(auto v : vec[it])
        {
            if(vis[v]!=0) continue;
            vis[v]=1;
            par[v]=it;
        }
    }
    for(int i=1; i<=n; i++) printf("%lld ", par[i]);
    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%lld", &n);
      |     ~~~~~^~~~~~~~~~~~
circle_selection.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%lld%lld%lld", &x[i], &y[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13