oj.uz

Submission #514346

# Submission time Handle Problem Language Result Execution time Memory
514346 2022-01-18T06:55:40 Z chenwz Park (BOI16_park) C++11
100 / 100
 492 ms 25432 KB 
// Baltic OI 2016 Park
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define _all(i, a, b) for (int i = (a); i <= (int)(b); ++i)
const int NN = 2008;
struct Circle {
  int x, y, r;
  int dist(const Circle& c) const {
    LL dx = x - c.x, dy = y - c.y;
    return sqrt(dx * dx + dy * dy);
  }
} T[NN];
struct Edge {
  int u, v, d;
  bool operator<(const Edge& e) const { return d < e.d; }
};
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int N, M, W, H, Pw[5][5];
  cin >> N >> M >> W >> H;
  const int BW = N + 1, BN = N + 2, BE = N + 3, BS = N + 4;  // 西北东南边界
  vector<int> fa(N + 5);
  _all(i, 1, N + 4) fa[i] = i; // 并查集  
  function<int(int)> findset = [&](int u) {
    return fa[u] == u ? u : fa[u] = findset(fa[u]);
  };
  vector<Edge> es;  // edges
  auto add_e = [&es](int u, int v, int d) { es.push_back({u, v, d}); };
  _all(i, 1, N) {
    Circle& c = T[i];
    cin >> c.x >> c.y >> c.r;
    add_e(i, BW, c.x - c.r), add_e(i, BN, c.y - c.r);
    add_e(i, BE, W - c.x - c.r), add_e(i, BS, H - c.y - c.r);
    _all(j, 1, i - 1) add_e(i, j, c.dist(T[j]) - c.r - T[j].r);
  }
  memset(Pw, 0x7f, sizeof(Pw));  // (1:左下, 2:右下, 3:右上, 4:左上).
  sort(es.begin(), es.end());
  for (const Edge& e : es) {
    fa[findset(e.u)] = fa[findset(e.v)];
    int bw = findset(BW), bn = findset(BN), be = findset(BE), bs = findset(BS);
    if (bn == bw || bn == be || bn == bs)
      Pw[1][2] = min(Pw[1][2], e.d);  // 左下--右下路上的最窄点
    if (bw == bn || bw == be || bw == bs)
      Pw[1][4] = min(Pw[1][4], e.d);  // 左下--左上路上的最窄点
    if (be == bw || be == bn || be == bs)
      Pw[2][3] = min(Pw[2][3], e.d);  // 右下--右上路上的最窄点
    if (bs == bw || bs == bn || bs == be)
      Pw[3][4] = min(Pw[3][4], e.d);  // 右上--左上路上的最窄点
    if (bw == be || bw == bs || bn == be || bn == bs)
      Pw[2][4] = min(Pw[2][4], e.d);  // 右下--左上路上的最窄点
    if (bw == bn || bw == be || bs == bn || bs == be)
      Pw[1][3] = min(Pw[1][3], e.d);  // 左下--右上路上的最窄点
  }
  for (int i = 0, r, e; i < M; i++) {
    cin >> r >> e, r *= 2;
    _all(i, 1, e - 1) if (Pw[i][e] >= r) cout << i;
    cout << e;
    _all(i, e + 1, 4) if (Pw[e][i] >= r) cout << i;
    cout << endl;
  }
  return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 25132 KB Output is correct
2 Correct 332 ms 25080 KB Output is correct
3 Correct 354 ms 25140 KB Output is correct
4 Correct 351 ms 25176 KB Output is correct
5 Correct 355 ms 25140 KB Output is correct
6 Correct 342 ms 25104 KB Output is correct
7 Correct 293 ms 25132 KB Output is correct
8 Correct 291 ms 25108 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 2092 KB Output is correct
2 Correct 135 ms 1952 KB Output is correct
3 Correct 143 ms 1916 KB Output is correct
4 Correct 146 ms 2040 KB Output is correct
5 Correct 155 ms 2100 KB Output is correct
6 Correct 143 ms 2008 KB Output is correct
7 Correct 137 ms 1748 KB Output is correct
8 Correct 136 ms 1720 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 25132 KB Output is correct
2 Correct 332 ms 25080 KB Output is correct
3 Correct 354 ms 25140 KB Output is correct
4 Correct 351 ms 25176 KB Output is correct
5 Correct 355 ms 25140 KB Output is correct
6 Correct 342 ms 25104 KB Output is correct
7 Correct 293 ms 25132 KB Output is correct
8 Correct 291 ms 25108 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 145 ms 2092 KB Output is correct
12 Correct 135 ms 1952 KB Output is correct
13 Correct 143 ms 1916 KB Output is correct
14 Correct 146 ms 2040 KB Output is correct
15 Correct 155 ms 2100 KB Output is correct
16 Correct 143 ms 2008 KB Output is correct
17 Correct 137 ms 1748 KB Output is correct
18 Correct 136 ms 1720 KB Output is correct
19 Correct 485 ms 25388 KB Output is correct
20 Correct 476 ms 25316 KB Output is correct
21 Correct 492 ms 25420 KB Output is correct
22 Correct 478 ms 25360 KB Output is correct
23 Correct 486 ms 25340 KB Output is correct
24 Correct 436 ms 25432 KB Output is correct