oj.uz

Submission #223976

# Submission time Handle Problem Language Result Execution time Memory
223976 2020-04-16T23:36:16 Z Bruteforceman Park (BOI16_park) C++11
100 / 100
 872 ms 73296 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) {
      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) {
           ~~^~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 66200 KB Output is correct
2 Correct 482 ms 66076 KB Output is correct
3 Correct 480 ms 66244 KB Output is correct
4 Correct 483 ms 66364 KB Output is correct
5 Correct 496 ms 66200 KB Output is correct
6 Correct 482 ms 66232 KB Output is correct
7 Correct 464 ms 66072 KB Output is correct
8 Correct 463 ms 66232 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 9120 KB Output is correct
2 Correct 348 ms 9452 KB Output is correct
3 Correct 345 ms 8812 KB Output is correct
4 Correct 369 ms 9588 KB Output is correct
5 Correct 395 ms 9704 KB Output is correct
6 Correct 340 ms 7148 KB Output is correct
7 Correct 320 ms 7276 KB Output is correct
8 Correct 339 ms 7272 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 66200 KB Output is correct
2 Correct 482 ms 66076 KB Output is correct
3 Correct 480 ms 66244 KB Output is correct
4 Correct 483 ms 66364 KB Output is correct
5 Correct 496 ms 66200 KB Output is correct
6 Correct 482 ms 66232 KB Output is correct
7 Correct 464 ms 66072 KB Output is correct
8 Correct 463 ms 66232 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 363 ms 9120 KB Output is correct
12 Correct 348 ms 9452 KB Output is correct
13 Correct 345 ms 8812 KB Output is correct
14 Correct 369 ms 9588 KB Output is correct
15 Correct 395 ms 9704 KB Output is correct
16 Correct 340 ms 7148 KB Output is correct
17 Correct 320 ms 7276 KB Output is correct
18 Correct 339 ms 7272 KB Output is correct
19 Correct 801 ms 71380 KB Output is correct
20 Correct 810 ms 72532 KB Output is correct
21 Correct 821 ms 72660 KB Output is correct
22 Correct 845 ms 72704 KB Output is correct
23 Correct 872 ms 73296 KB Output is correct
24 Correct 787 ms 72452 KB Output is correct