oj.uz

Submission #223977

# Submission time Handle Problem Language Result Execution time Memory
223977 2020-04-16T23:38:23 Z Bruteforceman Park (BOI16_park) C++11
100 / 100
 608 ms 72152 KB 
#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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 66236 KB Output is correct
2 Correct 472 ms 66204 KB Output is correct
3 Correct 478 ms 66204 KB Output is correct
4 Correct 492 ms 66204 KB Output is correct
5 Correct 477 ms 66236 KB Output is correct
6 Correct 479 ms 66236 KB Output is correct
7 Correct 451 ms 66232 KB Output is correct
8 Correct 464 ms 66204 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 9072 KB Output is correct
2 Correct 136 ms 9560 KB Output is correct
3 Correct 132 ms 8812 KB Output is correct
4 Correct 109 ms 9584 KB Output is correct
5 Correct 121 ms 9780 KB Output is correct
6 Correct 89 ms 7152 KB Output is correct
7 Correct 81 ms 6132 KB Output is correct
8 Correct 83 ms 6132 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 66236 KB Output is correct
2 Correct 472 ms 66204 KB Output is correct
3 Correct 478 ms 66204 KB Output is correct
4 Correct 492 ms 66204 KB Output is correct
5 Correct 477 ms 66236 KB Output is correct
6 Correct 479 ms 66236 KB Output is correct
7 Correct 451 ms 66232 KB Output is correct
8 Correct 464 ms 66204 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 125 ms 9072 KB Output is correct
12 Correct 136 ms 9560 KB Output is correct
13 Correct 132 ms 8812 KB Output is correct
14 Correct 109 ms 9584 KB Output is correct
15 Correct 121 ms 9780 KB Output is correct
16 Correct 89 ms 7152 KB Output is correct
17 Correct 81 ms 6132 KB Output is correct
18 Correct 83 ms 6132 KB Output is correct
19 Correct 575 ms 70360 KB Output is correct
20 Correct 569 ms 71512 KB Output is correct
21 Correct 608 ms 71616 KB Output is correct
22 Correct 579 ms 71772 KB Output is correct
23 Correct 574 ms 72152 KB Output is correct
24 Correct 553 ms 71640 KB Output is correct