oj.uz

Submission #260879

# Submission time Handle Problem Language Result Execution time Memory
260879 2020-08-11T06:39:02 Z wiwiho Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 1048580 KB 
#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

ll dis(pll a, pll b){
    ll x = a.F - b.F;
    ll y = a.S - b.S;
    return x * x + y *y ;
}

struct Comp{

    bool operator()(pll a, pll b){
        if(a.F == b.F) return a.S < b.S;
        return a.F > b.F;
    }

};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<pair<ll, pll>> c(n);

    for(int i = 0; i < n; i++){
        cin >> c[i].S.F >> c[i].S.S >> c[i].F;
    }
    
    vector<int> a(n);

    vector<vector<int>> is(n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(dis(c[i].S, c[j].S) <= (c[i].F + c[j].F) * (c[i].F + c[j].F))
                is[i].eb(j);
        }
    }

    set<pll, Comp> pq;
    for(int i = 0; i < n; i++) pq.insert(mp(c[i].F, i));

    while(!pq.empty()){
        int now = pq.begin()->S;
        pq.erase(pq.begin());
        a[now] = now;
        for(int i : is[now]){
            if(pq.find(mp(c[i].F, i)) != pq.end()){
                a[i] = now;
                pq.erase(mp(c[i].F, i));
            }
        }
    }

    for(int i = 0; i < n; i++) cout << a[i] + 1 << " ";
    cout << "\n";

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 13 ms 4224 KB Output is correct
17 Correct 12 ms 4032 KB Output is correct
18 Correct 13 ms 4480 KB Output is correct
19 Correct 231 ms 116064 KB Output is correct
20 Correct 217 ms 119032 KB Output is correct
21 Correct 285 ms 75000 KB Output is correct
22 Correct 92 ms 1272 KB Output is correct
23 Correct 95 ms 1272 KB Output is correct
24 Correct 83 ms 1272 KB Output is correct
25 Correct 84 ms 1272 KB Output is correct
26 Correct 108 ms 1272 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2858 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Execution timed out 3077 ms 8824 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 3061 ms 23980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 13 ms 4224 KB Output is correct
17 Correct 12 ms 4032 KB Output is correct
18 Correct 13 ms 4480 KB Output is correct
19 Correct 231 ms 116064 KB Output is correct
20 Correct 217 ms 119032 KB Output is correct
21 Correct 285 ms 75000 KB Output is correct
22 Correct 92 ms 1272 KB Output is correct
23 Correct 95 ms 1272 KB Output is correct
24 Correct 83 ms 1272 KB Output is correct
25 Correct 84 ms 1272 KB Output is correct
26 Correct 108 ms 1272 KB Output is correct
27 Correct 1052 ms 331800 KB Output is correct
28 Correct 871 ms 401936 KB Output is correct
29 Correct 895 ms 388600 KB Output is correct
30 Correct 342 ms 2168 KB Output is correct
31 Correct 324 ms 2216 KB Output is correct
32 Correct 356 ms 2168 KB Output is correct
33 Runtime error 2635 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 13 ms 4224 KB Output is correct
17 Correct 12 ms 4032 KB Output is correct
18 Correct 13 ms 4480 KB Output is correct
19 Correct 231 ms 116064 KB Output is correct
20 Correct 217 ms 119032 KB Output is correct
21 Correct 285 ms 75000 KB Output is correct
22 Correct 92 ms 1272 KB Output is correct
23 Correct 95 ms 1272 KB Output is correct
24 Correct 83 ms 1272 KB Output is correct
25 Correct 84 ms 1272 KB Output is correct
26 Correct 108 ms 1272 KB Output is correct
27 Runtime error 2858 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Halted 0 ms 0 KB -