oj.uz

Submission #514255

# Submission time Handle Problem Language Result Execution time Memory
514255 2022-01-18T05:54:24 Z chenwz Park (BOI16_park) C++11
100 / 100
 315 ms 49832 KB 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int NN = 2008;
struct node {
  LL x, y, r;
} a[2001];
struct Edge {
  LL u, v, d;
  bool operator<(const Edge& e) const {
    return d < e.d;
  }
};
LL N, m, cnt, fa[NN];
LL dis(node i, node j) {
  return sqrt((i.x - j.x) * (i.x - j.x) + (i.y - j.y) * (i.y - j.y));
}
LL ans[5][5], w, h;
LL find(LL i) { return fa[i] == i ? i : fa[i] = find(fa[i]); }
signed main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> N >> m >> w >> h;
  for (int i = 1; i <= NN; i++) fa[i] = i;
  for (int i = 1; i <= N; i++) cin >> a[i].x >> a[i].y >> a[i].r;
  for (int i = 1; i <= 4; i++)
    for (int j = 1; j < i; j++) ans[i][j] = ans[j][i] = 1e18;

  vector<Edge> b;
  for (int i = 1; i <= N; i++)
    for (int j = 1; j < i; j++)
      b.push_back({i, j, dis(a[i], a[j]) - a[i].r - a[j].r});
  for (int i = 1; i <= N; i++)
    b.push_back({i, N + 1, a[i].x - a[i].r}),
    b.push_back({i, N + 2, a[i].y - a[i].r}),
    b.push_back({i, N + 3, w - a[i].x - a[i].r}),
    b.push_back({i, N + 4, h - a[i].y - a[i].r});
  // sort(b + 1, b + cnt + 1, cmp);
  sort(b.begin(), b.end());
  for (size_t i = 0; i < b.size(); i++) {
    fa[find(b[i].u)] = fa[find(b[i].v)], find(N + 1), find(N + 2), find(N + 3),
    find(N + 4);
    if (fa[N + 2] == fa[N + 1] || fa[N + 2] == fa[N + 3] ||
        fa[N + 2] == fa[N + 4])
      ans[1][2] = min(ans[1][2], b[i].d);
    if (fa[N + 1] == fa[N + 2] || fa[N + 1] == fa[N + 3] ||
        fa[N + 1] == fa[N + 4])
      ans[1][4] = min(ans[1][4], b[i].d);
    if (fa[N + 3] == fa[N + 1] || fa[N + 3] == fa[N + 2] ||
        fa[N + 3] == fa[N + 4])
      ans[2][3] = min(ans[2][3], b[i].d);
    if (fa[N + 4] == fa[N + 1] || fa[N + 4] == fa[N + 2] ||
        fa[N + 4] == fa[N + 3])
      ans[3][4] = min(ans[3][4], b[i].d);
    if (fa[N + 1] == fa[N + 3] || fa[N + 1] == fa[N + 4] ||
        fa[N + 2] == fa[N + 3] || fa[N + 2] == fa[N + 4])
      ans[2][4] = min(ans[2][4], b[i].d);
    if (fa[N + 1] == fa[N + 2] || fa[N + 1] == fa[N + 3] ||
        fa[N + 4] == fa[N + 2] || fa[N + 4] == fa[N + 3])
      ans[1][3] = min(ans[1][3], b[i].d);
  }
  while (m--) {
    int r, e;
    cin>>r>>e;
    for (int i = 1; i < e; i++)
      if (ans[i][e] >= r * 2) putchar(i + 48);  //注意输入的是半径需要乘2
    putchar(e + 48);
    for (LL i = e + 1; i <= 4; i++)
      if (ans[e][i] >= r * 2) putchar(i + 48);
    puts("");
  }
  return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:24:39: warning: iteration 2007 invokes undefined behavior [-Waggressive-loop-optimizations]
   24 |   for (int i = 1; i <= NN; i++) fa[i] = i;
      |                                 ~~~~~~^~~
park.cpp:24:21: note: within this loop
   24 |   for (int i = 1; i <= NN; i++) fa[i] = i;
      |                   ~~^~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 49720 KB Output is correct
2 Correct 282 ms 49828 KB Output is correct
3 Correct 272 ms 49832 KB Output is correct
4 Correct 292 ms 49732 KB Output is correct
5 Correct 273 ms 49804 KB Output is correct
6 Correct 277 ms 49792 KB Output is correct
7 Correct 246 ms 49832 KB Output is correct
8 Correct 248 ms 49752 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1580 KB Output is correct
2 Correct 21 ms 1476 KB Output is correct
3 Correct 26 ms 1444 KB Output is correct
4 Correct 23 ms 1472 KB Output is correct
5 Correct 21 ms 1520 KB Output is correct
6 Correct 21 ms 1536 KB Output is correct
7 Correct 19 ms 836 KB Output is correct
8 Correct 24 ms 812 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 49720 KB Output is correct
2 Correct 282 ms 49828 KB Output is correct
3 Correct 272 ms 49832 KB Output is correct
4 Correct 292 ms 49732 KB Output is correct
5 Correct 273 ms 49804 KB Output is correct
6 Correct 277 ms 49792 KB Output is correct
7 Correct 246 ms 49832 KB Output is correct
8 Correct 248 ms 49752 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 29 ms 1580 KB Output is correct
12 Correct 21 ms 1476 KB Output is correct
13 Correct 26 ms 1444 KB Output is correct
14 Correct 23 ms 1472 KB Output is correct
15 Correct 21 ms 1520 KB Output is correct
16 Correct 21 ms 1536 KB Output is correct
17 Correct 19 ms 836 KB Output is correct
18 Correct 24 ms 812 KB Output is correct
19 Correct 292 ms 49764 KB Output is correct
20 Correct 298 ms 49728 KB Output is correct
21 Correct 314 ms 49768 KB Output is correct
22 Correct 287 ms 49696 KB Output is correct
23 Correct 315 ms 49696 KB Output is correct
24 Correct 302 ms 49788 KB Output is correct