oj.uz

Submission #971556

# Submission time Handle Problem Language Result Execution time Memory
971556 2024-04-29T00:28:24 Z irmuun Circle selection (APIO18_circle_selection) C++17
7 / 100
 3000 ms 1048576 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=3e5+5;
ll n;
ll x[N],y[N],r[N];
vector<ll>adj[N],ans(N,0);
vector<bool>used(N,0);

ll dist(ll i,ll j){
    return abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    set<pair<ll,ll>>st;
    for(ll i=1;i<=n;i++){
        cin>>x[i]>>y[i]>>r[i];
        st.insert({-r[i],i});
    }
    for(ll i=1;i<=n;i++){
        for(ll j=i+1;j<=n;j++){
            if(dist(i,j)<=(r[i]+r[j])*(r[i]+r[j])){
                adj[i].pb(j);
                adj[j].pb(i);
            }
        }
    }
    while(!st.empty()){
        ll i=st.begin()->ss;
        st.erase(st.begin());
        if(ans[i]>0) continue;
        ans[i]=i;
        for(ll j:adj[i]){
            if(ans[j]==0) ans[j]=i;
        }
    }
    for(ll i=1;i<=n;i++){
        cout<<ans[i]<<' ';
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 3 ms 15196 KB Output is correct
5 Correct 3 ms 15196 KB Output is correct
6 Correct 4 ms 15448 KB Output is correct
7 Correct 3 ms 15452 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct
9 Correct 3 ms 15192 KB Output is correct
10 Correct 4 ms 15196 KB Output is correct
11 Correct 4 ms 15336 KB Output is correct
12 Correct 3 ms 15196 KB Output is correct
13 Correct 3 ms 15196 KB Output is correct
14 Correct 3 ms 15196 KB Output is correct
15 Correct 3 ms 15196 KB Output is correct
16 Correct 11 ms 23640 KB Output is correct
17 Correct 11 ms 23384 KB Output is correct
18 Correct 11 ms 24156 KB Output is correct
19 Correct 248 ms 269684 KB Output is correct
20 Correct 258 ms 270524 KB Output is correct
21 Correct 203 ms 172708 KB Output is correct
22 Correct 20 ms 15780 KB Output is correct
23 Correct 20 ms 15704 KB Output is correct
24 Correct 21 ms 15704 KB Output is correct
25 Correct 19 ms 15780 KB Output is correct
26 Correct 19 ms 15708 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2369 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Execution timed out 3085 ms 21636 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3028 ms 35664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 3 ms 15196 KB Output is correct
5 Correct 3 ms 15196 KB Output is correct
6 Correct 4 ms 15448 KB Output is correct
7 Correct 3 ms 15452 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct
9 Correct 3 ms 15192 KB Output is correct
10 Correct 4 ms 15196 KB Output is correct
11 Correct 4 ms 15336 KB Output is correct
12 Correct 3 ms 15196 KB Output is correct
13 Correct 3 ms 15196 KB Output is correct
14 Correct 3 ms 15196 KB Output is correct
15 Correct 3 ms 15196 KB Output is correct
16 Correct 11 ms 23640 KB Output is correct
17 Correct 11 ms 23384 KB Output is correct
18 Correct 11 ms 24156 KB Output is correct
19 Correct 248 ms 269684 KB Output is correct
20 Correct 258 ms 270524 KB Output is correct
21 Correct 203 ms 172708 KB Output is correct
22 Correct 20 ms 15780 KB Output is correct
23 Correct 20 ms 15704 KB Output is correct
24 Correct 21 ms 15704 KB Output is correct
25 Correct 19 ms 15780 KB Output is correct
26 Correct 19 ms 15708 KB Output is correct
27 Correct 954 ms 745276 KB Output is correct
28 Correct 1113 ms 916808 KB Output is correct
29 Correct 1080 ms 881840 KB Output is correct
30 Correct 66 ms 16220 KB Output is correct
31 Correct 64 ms 16220 KB Output is correct
32 Correct 112 ms 16216 KB Output is correct
33 Runtime error 1574 ms 1048576 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 3 ms 15196 KB Output is correct
5 Correct 3 ms 15196 KB Output is correct
6 Correct 4 ms 15448 KB Output is correct
7 Correct 3 ms 15452 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct
9 Correct 3 ms 15192 KB Output is correct
10 Correct 4 ms 15196 KB Output is correct
11 Correct 4 ms 15336 KB Output is correct
12 Correct 3 ms 15196 KB Output is correct
13 Correct 3 ms 15196 KB Output is correct
14 Correct 3 ms 15196 KB Output is correct
15 Correct 3 ms 15196 KB Output is correct
16 Correct 11 ms 23640 KB Output is correct
17 Correct 11 ms 23384 KB Output is correct
18 Correct 11 ms 24156 KB Output is correct
19 Correct 248 ms 269684 KB Output is correct
20 Correct 258 ms 270524 KB Output is correct
21 Correct 203 ms 172708 KB Output is correct
22 Correct 20 ms 15780 KB Output is correct
23 Correct 20 ms 15704 KB Output is correct
24 Correct 21 ms 15704 KB Output is correct
25 Correct 19 ms 15780 KB Output is correct
26 Correct 19 ms 15708 KB Output is correct
27 Runtime error 2369 ms 1048576 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -