Submission #1272316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272316		rtri	Park (BOI16_park)	C++20	0 / 100	227 ms	125704 KiB

park

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef double db;

int n, m, w, h;
vector<tuple<int, int, int>> trees;
vector<tuple<int, int, int>> queries;

struct UF {
  vector<int> sz, p;

public:
  UF(int n) : sz(n, 1), p(n, -1) {}
  int find(int a) { return p[a] < 0 ? a : p[a] = find(p[a]); }
  bool join(int a, int b) {
    a = find(a), b = find(b);
    if (a == b)
      return false;
    if (sz[a] < sz[b])
      swap(a, b);
    sz[a] += sz[b];
    p[b] = a;
    return true;
  }
};

int bottomleft = 1;
int bottomright = 2;
int topright = 4;
int topleft = 8;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> m >> w >> h;

  int edtop = n;
  int edlef = n + 1;
  int edrig = n + 2;
  int edbot = n + 3;

  for (int i = 0; i < n; i++) {
    int x, y, r;
    cin >> x >> y >> r;
    trees.push_back({x, y, r});
  }

  for (int i = 0; i < m; i++) {
    int r, e;
    cin >> r >> e;
    queries.push_back({r * 2, e, i});
  }
  sort(queries.begin(), queries.end());

  vector<tuple<db, int, int>> edg(n * n);
  for (int i = 0; i < n - 1; i++)
    for (int j = i + 1; j < n; j++) {
      auto [x1, y1, r1] = trees[i];
      auto [x2, y2, r2] = trees[j];
      db dist = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
      edg[i * n + j] = {max((db)0, sqrt(dist) - r1 - r2), i, j};
    }
  for (int i = 0; i < n; i++) {
    auto [x, y, r] = trees[i];
    edg.push_back({max(0, y - r), i, edbot});
    edg.push_back({max(0, x - r), i, edlef});
    edg.push_back({max(0, h - y - r), i, edtop});
    edg.push_back({max(0, w - x - r), i, edrig});
  }
  sort(edg.begin(), edg.end());

  UF uf(n + 4);
  vector<int> ans(queries.size());

  int edg_it = 0;
  for (auto [d, e, qi] : queries) {
    while (edg_it < edg.size()) {
      auto [dist, i, j] = edg[edg_it];
      if (abs(dist - d) < 1e-15)
        uf.join(i, j);
      else
        break;
      edg_it++;
    }

    int c = 1 << (e - 1);
    int qans = bottomleft | bottomright | topright | topleft;
    if (uf.find(edlef) == uf.find(edtop)) {
      if (c == topleft)
        qans = topleft;
      else
        qans &= ~topleft;
    }

    if (uf.find(edtop) == uf.find(edrig)) {
      if (c == topright)
        qans = topright;
      else
        qans &= ~topright;
    }

    if (uf.find(edrig) == uf.find(edbot)) {
      if (c == bottomright)
        qans = bottomright;
      else
        qans &= ~bottomright;
    }

    if (uf.find(edbot) == uf.find(edlef)) {
      if (c == bottomleft)
        qans = bottomleft;
      else
        qans &= ~bottomleft;
    }

    if (uf.find(edlef) == uf.find(edrig)) {
      if (c == bottomleft || c == bottomright)
        qans &= ~(topleft | topright);
      else
        qans &= ~(bottomleft | bottomright);
    }

    if (uf.find(edtop) == uf.find(edbot)) {
      if (c == bottomleft || c == topleft)
        qans &= ~(topright | bottomright);
      else
        qans &= ~(bottomleft | topleft);
    }

    ans[qi] = qans;
  }

  for (int i = 0; i < m; i++) {
    for (int exit = 1; exit <= 4; exit++)
      if (ans[i] & (1 << (exit - 1)))
        cout << exit;
    cout << "\n";
  }

  cout << flush;

  return 0;
}

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