Submission #1087886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087886		alexander707070	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3080 ms	1048576 KiB

circle_selection

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

int n,par[MAXN];
long long x[MAXN],y[MAXN],r[MAXN];
pair<int,int> p[MAXN];

vector<int> g[MAXN];

int main(){

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i]>>r[i];

        p[i]={r[i],-i};
    }

    sort(p+1,p+n+1);

    for(int i=1;i<=n;i++){
        for(int f=i+1;f<=n;f++){
            if((x[i]-x[f])*(x[i]-x[f]) + (y[i]-y[f])*(y[i]-y[f]) <= (r[i]+r[f])*(r[i]+r[f])){
                g[i].push_back(f);
                g[f].push_back(i);
            }
        }
    }

    for(int i=n;i>=1;i--){
        int curr=-p[i].second;
        if(par[curr]!=0)continue;

        par[curr]=curr;
        for(int f=0;f<g[curr].size();f++){
            if(par[g[curr][f]]==0)par[g[curr][f]]=curr;
        }
    }

    for(int i=1;i<=n;i++){
        cout<<par[i]<<" ";
    }
    cout<<"\n";

    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int f=0;f<g[curr].size();f++){
      |                     ~^~~~~~~~~~~~~~~

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