# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
475175 | 2021-09-21T10:39:07 Z | khr03ae | Circle selection (APIO18_circle_selection) | C++14 | 58 ms | 1028 KB |
#include <bits/stdc++.h> using namespace std; typedef long long i64; const int MAX = 5e3 + 9; struct Circle { i64 x, y; i64 radius; i64 index; } circles[MAX]; int N, par[MAX]; bool deleted[MAX]; void init() { for (int i = 0; i < N; ++i) { par[i] = i; deleted[i] = false; } } bool cmp(Circle& a, Circle& b) { if (a.radius == b.radius) return a.index < b.index; return a.radius > b.radius; } bool intercept(Circle& a, Circle& b) { i64 dx = a.x - b.x; i64 dy = a.y - b.y; i64 dist2 = dx * dx * 1LL + dy * dy * 1LL; i64 r2 = (a.radius * 1LL + b.radius * 1LL) * (a.radius * 1LL + b.radius * 1LL) * 1LL; if (dist2 <= r2) { return true; } else { return false; } } int main() { scanf("%d", &N); for (int i = 0; i < N; ++i) { scanf("%lld%lld%lld", &circles[i].x, &circles[i].y, &circles[i].radius); circles[i].index = i; } sort(circles, circles + N, cmp); init(); // for (int i = 0; i < N; ++i) { // printf("%d %d %d %d\n", circles[i].x, circles[i].y, circles[i].radius, circles[i].index); // } for (int i = 0; i < N; ++i) { int u = circles[i].index; if (deleted[u]) continue; for (int j = 0; j < N; ++j) { int v = circles[j].index; if (intercept(circles[i], circles[j]) && !deleted[v]) { par[v] = u; deleted[v] = true; } } deleted[u] = true; } for (int i = 0; i < N; ++i) { printf("%d ", par[i] + 1); } printf("\n"); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 300 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 1 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 204 KB | Output is correct |
13 | Correct | 1 ms | 204 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 204 KB | Output is correct |
16 | Correct | 1 ms | 316 KB | Output is correct |
17 | Correct | 2 ms | 332 KB | Output is correct |
18 | Correct | 1 ms | 332 KB | Output is correct |
19 | Correct | 3 ms | 568 KB | Output is correct |
20 | Correct | 4 ms | 604 KB | Output is correct |
21 | Correct | 4 ms | 588 KB | Output is correct |
22 | Correct | 47 ms | 708 KB | Output is correct |
23 | Correct | 44 ms | 592 KB | Output is correct |
24 | Correct | 48 ms | 588 KB | Output is correct |
25 | Correct | 58 ms | 588 KB | Output is correct |
26 | Correct | 45 ms | 588 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 3 ms | 716 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Runtime error | 3 ms | 984 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 3 ms | 716 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 300 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 1 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 204 KB | Output is correct |
13 | Correct | 1 ms | 204 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 204 KB | Output is correct |
16 | Correct | 1 ms | 316 KB | Output is correct |
17 | Correct | 2 ms | 332 KB | Output is correct |
18 | Correct | 1 ms | 332 KB | Output is correct |
19 | Correct | 3 ms | 568 KB | Output is correct |
20 | Correct | 4 ms | 604 KB | Output is correct |
21 | Correct | 4 ms | 588 KB | Output is correct |
22 | Correct | 47 ms | 708 KB | Output is correct |
23 | Correct | 44 ms | 592 KB | Output is correct |
24 | Correct | 48 ms | 588 KB | Output is correct |
25 | Correct | 58 ms | 588 KB | Output is correct |
26 | Correct | 45 ms | 588 KB | Output is correct |
27 | Runtime error | 4 ms | 1028 KB | Execution killed with signal 11 |
28 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 300 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 1 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 204 KB | Output is correct |
13 | Correct | 1 ms | 204 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 204 KB | Output is correct |
16 | Correct | 1 ms | 316 KB | Output is correct |
17 | Correct | 2 ms | 332 KB | Output is correct |
18 | Correct | 1 ms | 332 KB | Output is correct |
19 | Correct | 3 ms | 568 KB | Output is correct |
20 | Correct | 4 ms | 604 KB | Output is correct |
21 | Correct | 4 ms | 588 KB | Output is correct |
22 | Correct | 47 ms | 708 KB | Output is correct |
23 | Correct | 44 ms | 592 KB | Output is correct |
24 | Correct | 48 ms | 588 KB | Output is correct |
25 | Correct | 58 ms | 588 KB | Output is correct |
26 | Correct | 45 ms | 588 KB | Output is correct |
27 | Runtime error | 3 ms | 716 KB | Execution killed with signal 11 |
28 | Halted | 0 ms | 0 KB | - |