Submission #514346

#	Time	Username	Problem	Language	Result	Execution time	Memory
514346		chenwz	Park (BOI16_park)	C++11	100 / 100	492 ms	25432 KiB

park

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