Submission #256999

#	Time	Username	Problem	Language	Result	Execution time	Memory
256999		rama_pang	Park (BOI16_park)	C++14	31 / 100	2572 ms	1792 KiB

park

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

class DisjointSet {
 public:
  vector<int> p;
  DisjointSet() {}
  DisjointSet(int sz) : p(sz) {
    iota(begin(p), end(p), 0);
  }
  void Clear() {
    iota(begin(p), end(p), 0);
  }
  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }
  int Unite(int x, int y) {
    x = Find(x), y = Find(y);
    if (x != y) {
      p[x] = y;
      return 1;
    }
    return 0;
  }
  bool SameSet(int x, int y) {
    return Find(x) == Find(y);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, Q, H, W;
  cin >> N >> Q >> W >> H;
  vector<long long> X(N), Y(N), R(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i] >> R[i];
  }

  vector<long long> blocks(6);
  // blocks[0] = cover left to down
  // blocks[1] = cover down to right
  // blocks[2] = cover right to up
  // blocks[3] = cover up to left
  // blocks[4] = cover left to right
  // blocks[5] = cover up to down
  
  auto IsConnected = [&](long long rad, const function<bool(long long, long long)> &GA, 
                                        const function<bool(long long, long long)> &GB) -> bool {
    static DisjointSet D(N + 2);
    D.Clear();
    auto AddEdge = [&](int u, int v) {
      D.Unite(u, v);
    };
    for (int i = 0; i < N; i++) {
      if (GA(X[i] - 2ll * rad - R[i], Y[i]) || GA(X[i] + 2ll * rad + R[i], Y[i]) || 
          GA(X[i], Y[i] - 2ll * rad - R[i]) || GA(X[i], Y[i] + 2ll * rad + R[i])) {
        AddEdge(N + 0, i);
        if (D.SameSet(N, N + 1)) {
          return true;
        }
      }
      if (GB(X[i] - 2ll * rad - R[i], Y[i]) || GB(X[i] + 2ll * rad + R[i], Y[i]) || 
          GB(X[i], Y[i] - 2ll * rad - R[i]) || GB(X[i], Y[i] + 2ll * rad + R[i])) {
        AddEdge(N + 1, i);
        if (D.SameSet(N, N + 1)) {
          return true;
        }
      }
    }
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        if ((X[i] - X[j]) * (X[i] - X[j]) + 
            (Y[i] - Y[j]) * (Y[i] - Y[j]) < 
            (R[i] + R[j] + 2ll * rad) * (R[i] + R[j] + 2ll * rad)) {
          AddEdge(i, j);
          if (D.SameSet(N, N + 1)) {
            return true;
          }
        }
      }
    }
    return false;
  };

  auto Solve = [&](const function<bool(long long, long long)> &GA, const function<bool(long long, long long)> &GB) -> long long {
    long long lo = 0, hi = 1e9;
    while (lo < hi) {
      long long md = (lo + hi) / 2;
      if (IsConnected(md, GA, GB)) {
        hi = md;
      } else {
        lo = md + 1;
      }
    }
    return lo;
  };

  blocks[0] = Solve([&](long long x, long long y) { return x < 0; }, [&](long long x, long long y) { return y < 0; });
  blocks[1] = Solve([&](long long x, long long y) { return y < 0; }, [&](long long x, long long y) { return x > W; });
  blocks[2] = Solve([&](long long x, long long y) { return x > W; }, [&](long long x, long long y) { return y > H; });
  blocks[3] = Solve([&](long long x, long long y) { return y > H; }, [&](long long x, long long y) { return x < 0; });
  blocks[4] = Solve([&](long long x, long long y) { return x < 0; }, [&](long long x, long long y) { return x > W; });
  blocks[5] = Solve([&](long long x, long long y) { return y < 0; }, [&](long long x, long long y) { return y > H; });

  while (Q--) {
    int r, e;
    cin >> r >> e;
    e--;
    string ans;
    for (int i = 0; i < 4; i++) {
      long long b = min(blocks[e], blocks[i]);
      if (((e == 0 || e == 1) && (i == 2 || i == 3)) || ((i == 0 || i == 1) && (e == 2 || e == 3))) {
        b = min(b, blocks[4]);
      }
      if (((e == 0 || e == 3) && (i == 1 || i == 2)) || ((i == 0 || i == 3) && (e == 1 || e == 2))) {
        b = min(b, blocks[5]);
      }
      if (e == i || r < b) {
        ans.push_back('1' + i);
      }
    }
    cout << ans << "\n";
  }
  return 0;
}

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