Submission #513799

#	Time	Username	Problem	Language	Result	Execution time	Memory
513799		chenwz	Park (BOI16_park)	C++11	100 / 100	891 ms	56404 KiB

park

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define _all(i, a, b) for (int i = (a); i <= (int)(b); ++i)

const int VV = 5050;
int T, P, W, H, fa[VV];
struct Circle {
  int x, y, r;
};

Circle Ts[VV];
int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }
void unite(int a, int b) { a = find(a), b = find(b), fa[a] = b; }
// Trees T, T + 1, T + 2, T + 3 are the bottom, right, top and left borders.
bool overlap(int time, int i, int j) {
  const Circle &t1 = Ts[i], t2 = Ts[j];
  if (i >= T) {
    if (j >= T) return false;
    if (i == T) return t2.y - t2.r - time < time;
    if (i == T + 1) return t2.x + t2.r + time > W - time;
    if (i == T + 2) return t2.y + t2.r + time > H - time;
    if (i == T + 3) return t2.x - t2.r - time < time;
    throw 5;
    return false;
  } else {
    if (j >= T) return overlap(time, j, i);
    LL dx = t1.x - t2.x, dy = t1.y - t2.y;
    LL maxd2 = t1.r + t2.r + 2 * time;
    return dx * dx + dy * dy < maxd2 * maxd2;
  }
}

int main() {
  _for(i, 0, VV) fa[i] = i;
  cin.sync_with_stdio(false), cin.tie(0);
  cin >> T >> P;
  cin >> W >> H;
  _for(i, 0, T) cin >> Ts[i].x >> Ts[i].y >> Ts[i].r;

  using VI = vector<int>;
  vector<VI> Q(P);
  _for(i, 0, P) {
    int r, e;
    cin >> r >> e, Q[i] = {r, e - 1, i};
  }
  sort(Q.begin(), Q.end());
  vector<pair<LL, pair<LL, LL>>> es;  // (time, (tree1, tree2))
  _for(i, 0, T + 4) _for(j, i + 1, T + 4) {
    LL A = 0, B = W + H + 5;
    while (A != B) {
      LL M = (A + B) / 2;
      overlap(M, i, j) ? (B = M) : (A = M + 1);
    }
    es.emplace_back(A, make_pair(i, j));
  }
  sort(es.begin(), es.end());
  vector<array<bool, 4>> res(P);
  int ei = 0;
  for (auto q : Q) {
    while (ei < (int)es.size() && es[ei].first <= q[0]) {
      unite(es[ei].second.first, es[ei].second.second);
      ++ei;
    }
    int c = q[1];
    array<bool, 4>& r = res[q[2]];
    auto conn = [c](int a, int b) {
      return find(T + (c + a) % 4) == find(T + (c + b) % 4);
    };
    r[c] = true;
    if (!conn(0, 1) && !conn(0, 2) && !conn(0, 3)) r[(c + 1) % 4] = true;
    if (!conn(0, 2) && !conn(0, 3) && !conn(1, 2) && !conn(1, 3))
      r[(c + 2) % 4] = true;
    if (!conn(3, 0) && !conn(3, 1) && !conn(3, 2)) r[(c + 3) % 4] = true;
  }
  for (const auto& r : res) {
    _for(i, 0, 4) if (r[i]) cout << i + 1;
    cout << '\n';
  }
  return 0;
}

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