Submission #514255

#	Time	Username	Problem	Language	Result	Execution time	Memory
514255		chenwz	Park (BOI16_park)	C++11	100 / 100	315 ms	49832 KiB

park

#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 (stderr)

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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42