Submission #646413

#	Time	Username	Problem	Language	Result	Execution time	Memory
646413		Alex_tz307	Park (BOI16_park)	C++17	100 / 100	260 ms	26292 KiB

park

#include <bits/stdc++.h>

using namespace std;

const int kN = 2e3;
const int kM = 1e5;

int Edist(int x1, int y1, int x2, int y2) {
  return sqrtl((int64_t)(x1 - x2) * (x1 - x2) + (int64_t)(y1 - y2) * (y1 - y2));
}

struct circle_t {
  int x, y, r;

  void read() {
    cin >> x >> y >> r;
  }

  int dist(const circle_t &other) {
    return Edist(x, y, other.x, other.y) - r - other.r;
  }
} t[kN];

struct query_t {
  int r, e, index;

  void read() {
    cin >> r >> e;
    r *= 2;
    e -= 1;
  }

  bool operator < (const query_t &rhs) const {
    return r < rhs.r;
  }
} q[kM];

struct edge {
  int u, v, w;

  bool operator < (const edge &rhs) const {
    return w < rhs.w;
  }
};

struct DSU {
  vector<int> p, sz;

  void init(int n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
    sz.assign(n, 1);
  }

  int root(int x) {
    if (x == p[x]) {
      return x;
    }
    return p[x] = root(p[x]);
  }

  bool connected(int x, int y) {
    return root(x) == root(y);
  }

  bool unite(int u, int v) {
    int x = root(u), y = root(v);
    if (x == y) {
      return false;
    }
    if (sz[y] < sz[x]) {
      swap(x, y);
    }
    p[x] = y;
    sz[y] += sz[x];
    return true;
  }
} dsu;

int n;
short sol[kM];

void solveQuery(int p) {
  int e = q[p].e, index = q[p].index;
  sol[index] |= (1 << e);
  if (!dsu.connected(n + e, n + (e + 2) % 4) && !dsu.connected(n + e, n + (e + 3) % 4) && !dsu.connected(n + e, n + (e + 1) % 4)) {
    sol[index] |= (1 << ((e + 1) % 4));
  }
  if (!dsu.connected(n + e, n + (e + 3) % 4) && !dsu.connected(n + (e + 1) % 4, n + (e + 2) % 4) && !dsu.connected(n + e, n + (e + 2) % 4) && !dsu.connected(n + (e + 1) % 4, n + (e + 3) % 4)) {
    sol[index] |= (1 << ((e + 2) % 4));
  }
  if (!dsu.connected(n + e, n + (e + 3) % 4) && !dsu.connected(n + (e + 2) % 4, n + (e + 3) % 4) && !dsu.connected(n + (e + 1) % 4, n + (e + 3) % 4)) {
    sol[index] |= (1 << ((e + 3) % 4));
  }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int m, w, h;
  cin >> n >> m >> w >> h;

  for (int i = 0; i < n; ++i) {
    t[i].read();
  }

  for (int i = 0; i < m; ++i) {
    q[i].read();
    q[i].index = i;
  }

  vector<edge> edges;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      edges.push_back({i, j, t[i].dist(t[j])});
    }
    int x = t[i].x, y = t[i].y, r = t[i].r;
    edges.push_back({i, n, y - r});
    edges.push_back({i, n + 1, w - x - r});
    edges.push_back({i, n + 2, h - y - r});
    edges.push_back({i, n + 3, x - r});
  }

  sort(edges.begin(), edges.end());
  sort(q, q + m);

  dsu.init(n + 4);
  int ptr = 0;
  for (auto e : edges) {
    while (ptr < m && q[ptr].r <= e.w) {
      solveQuery(ptr);
      ptr += 1;
    }
    dsu.unite(e.u, e.v);
  }
  while (ptr < m) {
    solveQuery(ptr);
    ptr += 1;
  }

  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < 4; ++j) {
      if (sol[i] & (1 << j)) {
        cout << j + 1;
      }
    }
    cout << '\n';
  }

  return 0;
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42