Submission #1177376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177376		huydarwin	Circle selection (APIO18_circle_selection)	C++20	7 / 100	191 ms	125544 KiB

circle_selection

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ii pii
#define fi first
#define sc second
#define ll long long
#define pll pair<ll,ll>
#define ill pair<int,ll>
#define lli pair<ll,int>
#define inf 2000000000
#define INF inf
#define endl "\n"
#define pb push_back
#define eb emplace_back
#define llinf (ll)1e18
#define LLINF llinf
#define maxn 300005
#define maxm
#define task ""
using namespace std;

int n;
struct{
    ll x,y,r;
} a[maxn];

ll dist2(int u,int v){
    ll diffx = (a[u].x - a[v].x) * (a[u].x - a[v].x);
    ll diffy = (a[u].y - a[v].y) * (a[u].y - a[v].y);
    return diffx + diffy;
}

double dist(int u,int v){
    return sqrt(dist2(u,v));
}

bool intersect(int u,int v){
    return dist2(u,v) <= (a[u].r + a[v].r) * (a[u].r + a[v].r);
}

vector<int> adj[maxn];
int cnt;
int vt[maxn];
int cl[maxn];
int c[maxn];

void sub1(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            if(intersect(i,j)) adj[i].pb(j);
        }
    }
    for(int i=1;i<=n;i++) vt[i]=i;
    sort(vt+1,vt+n+1,[](auto u,auto v){
        return a[u].r > a[v].r;
    });
    for(int i=1;i<=n;i++) cl[i]=1;
    cnt=n;
    int j=1;
    while(cnt>0){
        while(j<=n && cl[vt[j]] == 0) j++;
        cnt--;
        cl[vt[j]]=0;
        c[vt[j]] = vt[j];
        for(auto u: adj[vt[j]]) if(cl[u] == 1){
            cnt--;
            cl[u] = 0;
            c[u] = vt[j];
        }
    }
    for(int i=1;i<=n;i++) cout<<c[i]<<" "; cout<<endl;
}

int main(){
    if (fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].r;
    if(n<=5000) sub1();

    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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