Submission #223977

#	Time	Username	Problem	Language	Result	Execution time	Memory
223977		Bruteforceman	Park (BOI16_park)	C++11	100 / 100	608 ms	72152 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define double long double
#define endl '\n'
const double eps = 1e-12;
const int maxn = 3005;
struct tree {
  int x, y, r;
} a[maxn];
typedef tree point;
int par[maxn];

double dist(point p, point q) {
  long long dx = p.x - q.x;
  long long dy = p.y - q.y;
  return sqrt(dx*dx + dy*dy);
}
int root(int x) {
  if(par[x] == x) return par[x];
  return par[x] = root(par[x]);
}
void join(int x, int y) {
  x = root(x);
  y = root(y);
  if(x != y) {
    par[x] = y;
  }
  return ;
}
int main() {
  ios_base :: sync_with_stdio (false);
  cin.tie (0);

  int n, m, h, w;
  cin >> n >> m >> w >> h;
  for(int i = 0; i < n; i++) {
    cin >> a[i].x >> a[i].y >> a[i].r;
  }
  vector <pair <double, pair <int, int>>> v;
  for(int i = 0; i < n; i++) {
    for(int j = i + 1; j < n; j++) {
      double gap = dist(a[i], a[j]) - a[i].r - a[j].r;
      v.emplace_back(gap, make_pair(i, j));
    }
    v.emplace_back(a[i].y - a[i].r, make_pair(i, n));
    v.emplace_back(w - a[i].x - a[i].r, make_pair(i, n + 1));
    v.emplace_back(h - a[i].y - a[i].r, make_pair(i, n + 2));
    v.emplace_back(a[i].x - a[i].r, make_pair(i, n + 3));
  }
  sort(v.begin(), v.end());
  int l = 0;
  
  vector <pair <int, int>> u;
  vector <pair <int, int>> original;
  for(int i = 0; i < m; i++) {
    int r, e;
    cin >> r >> e;
    u.emplace_back(r, e - 1);
  }
  original = u;
  sort(u.begin(), u.end());
  
  for(int i = 0; i < n + 4; i++) {
    par[i] = i;
  }
  map <pair <int, int>, string> mp;
  auto same = [&] (int i, int j) { return root(i) == root(j); };
  function <bool (int, int)> reach = [&] (int i, int j) {
    if(i == j) return true;
    if(same(n + i, n + (i + 3) % 4)) return false;
    if(same(n + j, n + (j + 3) % 4)) return false;
    if((i + 1) % 4 == j) {
      return !same(n + i, n + (i + 2) % 4);
    }
    if((j + 1) % 4 == i) {
      return !same(n + j, n + (j + 2) % 4);
    }
    for(int x = 0; x < 4; x++) {
      if(same(n + x, n + (x + 2) % 4)) return false;
    }
    return true;
  };
  for(int i = 0; i < m; i++) {
    while(l < v.size() && v[l].first < 2.0 * u[i].first) {
      join(v[l].second.first, v[l].second.second);
      ++l;
    }
    string res;
    for(int j = 0; j < 4; j++) {
      if(reach(u[i].second, j)) res += '0' + j + 1;
    }
    mp[u[i]] = res;
  }
  for(auto i : original) {
    cout << mp[i] << endl;
  }
  return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:84:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(l < v.size() && v[l].first < 2.0 * u[i].first) {
           ~~^~~~~~~~~~

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