oj.uz

Submission #223955

# Submission time Handle Problem Language Result Execution time Memory
223955 2020-04-16T22:28:18 Z Bruteforceman Park (BOI16_park) C++11
0 / 100
 362 ms 33356 KB 
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const int maxn = 3005;
struct tree {
  int x, y, r;
} a[maxn];
typedef tree point;
int par[maxn];

double dist(point p, point q) {
  int dx = p.x - q.x;
  int 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() {
  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 + eps) {
      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

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

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 319 ms 33356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 362 ms 8940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 319 ms 33356 KB Output isn't correct
2 Halted 0 ms 0 KB -