oj.uz

Submission #223961

# Submission time Handle Problem Language Result Execution time Memory
223961 2020-04-16T22:34:18 Z Bruteforceman Park (BOI16_park) C++11
0 / 100
 506 ms 66248 KB 
#include <bits/stdc++.h>
using namespace std;
#define double long double
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() {
  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:80: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 Correct 482 ms 66200 KB Output is correct
2 Correct 506 ms 66072 KB Output is correct
3 Correct 484 ms 66232 KB Output is correct
4 Correct 504 ms 66248 KB Output is correct
5 Correct 482 ms 66072 KB Output is correct
6 Correct 482 ms 66072 KB Output is correct
7 Correct 457 ms 66232 KB Output is correct
8 Incorrect 470 ms 66200 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 9120 KB Output is correct
2 Correct 350 ms 9452 KB Output is correct
3 Correct 345 ms 9060 KB Output is correct
4 Correct 344 ms 9448 KB Output is correct
5 Correct 351 ms 9708 KB Output is correct
6 Incorrect 338 ms 7140 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 66200 KB Output is correct
2 Correct 506 ms 66072 KB Output is correct
3 Correct 484 ms 66232 KB Output is correct
4 Correct 504 ms 66248 KB Output is correct
5 Correct 482 ms 66072 KB Output is correct
6 Correct 482 ms 66072 KB Output is correct
7 Correct 457 ms 66232 KB Output is correct
8 Incorrect 470 ms 66200 KB Output isn't correct
9 Halted 0 ms 0 KB -