Submission #1166850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166850		fryingduc	Park (BOI16_park)	C++20	100 / 100	239 ms	27564 KiB

park

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2005;
const int M = 1e5 + 5;
int n, m;
int w, h;
int x[maxn], y[maxn], r[maxn];
int qd[M], qr[M];
int ord[M];
int res[M][5];
int lab[maxn];
vector<pair<int, int>> ck[5][5];

int find(int u) {
  return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}

void join(int u, int v) {
  u = find(u), v = find(v);
  if (u == v) return;
  if (lab[u] > lab[v]) swap(u, v);
  lab[u] += lab[v];
  lab[v] = u;
}

pair<int, int> find_corner(int dir) {
  return make_pair(n + dir, n + (dir == 1 ? 4 : dir - 1));
}

void solve() {
  cin >> n >> m >> w >> h;
  for (int i = 1; i <= n; ++i) {
    cin >> x[i] >> y[i] >> r[i];
  }  
  vector<array<int, 3>> ccs;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j < i; ++j) {
      auto sq = [&](int x) -> long long {
        return 1ll * x * x;
      };
      long long d = sq(x[i] - x[j]) + sq(y[i] - y[j]);
      d = sqrtl(d);
      d -= r[i] + r[j];
      ccs.push_back({max(0, (int) d), i, j});
    }
    for (int t = 0; t < 4; ++t) {
      int d = 0;
      if (t == 0) d = y[i];
      if (t == 1) d = w - x[i];
      if (t == 2) d = h - y[i];
      if (t == 3) d = x[i];
      ccs.push_back({max(0, d - r[i]), i, n + t + 1});
    }
  }
  sort(ccs.begin(), ccs.end());
  for (int i = 1; i <= m; ++i) {
    cin >> qr[i] >> qd[i];
  }
  iota(ord + 1, ord + m + 1, 1);
  sort(ord + 1, ord + m + 1, [](const int &x, const int &y) -> bool {
    return qr[x] < qr[y];
  });
  memset(lab, -1, sizeof(lab));
  int ptr = 0;
  for (int i = 1; i <= m; ++i) {
    while (ptr < (int)ccs.size() and ccs[ptr][0] < 2 * qr[ord[i]]) {
      join(ccs[ptr][1], ccs[ptr][2]);
      ++ptr;
    }
    int dir = qd[ord[i]];
    auto wi = find_corner(dir);
    if (find(wi.second) == find(wi.first)) {
      res[ord[i]][dir] = 1;
      continue;
    }
    for (int j = 1; j <= 4; ++j) {
      if (j == dir) {
        res[ord[i]][j] = 1;
        continue;
      }
      auto wj = find_corner(j);
      if (find(wj.first) == find(wj.second)) continue;
      if (abs(dir - j) == 2) {
        res[ord[i]][j] = (find(n + 1) != find(n + 3)) & (find(n + 2) != find(n + 4));
      } else {
        pair<int, int> t = make_pair(min(dir, j), max(dir, j));
        if (t == make_pair(1, 4) || t == make_pair(2, 3)) {
          res[ord[i]][j] = find(n + 2) != find(n + 4);
        } else {
          res[ord[i]][j] = find(n + 1) != find(n + 3);
        }
      }
    }
  }
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= 4; ++j) {
      if (res[i][j]) cout << j;
    }
    cout << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/

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