oj.uz

Submission #724780

# Submission time Handle Problem Language Result Execution time Memory
724780 2023-04-16T00:33:44 Z vjudge1 Park (BOI16_park) C++17
100 / 100
 2147 ms 58304 KB 
#include "bits/stdc++.h"

using namespace std;
#define int long long
#define iii tuple<int,int,int>

const int ms = 2e3 + 10;

int sz[ms], ds[ms], esq[ms], dir[ms], up[ms], down[ms];

bool check(int x, int y, int a, int b, int r1, int r2){
  int dis = (x-a)*(x-a) + (y-b)*(y-b);
  if(dis < (r1+r2)*(r1+r2) && dis > (r1-r2)*(r1-r2)) return true;
  return false;
}

void init(vector<iii> &v){
  int i=0;
  for(auto[x, y, r] : v){
    sz[i] = 1;
    ds[i] = i;
    esq[i] = x - r;
    dir[i] = x + r;
    up[i] = y+r;
    down[i] = y-r;
    i++;
  }
}

int dsfind(int i){
  if(i != ds[i]) return ds[i] = dsfind(ds[i]);
  return ds[i];
}

void merge(int a, int b){
  a = dsfind(a);
  b = dsfind(b);
  if(a == b) return;
  if(sz[a] < sz[b]) swap(a, b);
  esq[a] = min(esq[a], esq[b]);
  down[a] = min(down[a], down[b]);
  dir[a] = max(dir[a], dir[b]);
  up[a] = max(up[a], up[b]);

  sz[a] += sz[b];
  ds[b] = a;
}

int32_t main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n, m, w, h;
  cin >> n >> m >> w >> h;

  vector<iii> coord(n);

  for(auto &[x, y, r] : coord) cin >> x >> y >> r;

  init(coord);

  vector<iii> qry(m);
  int aux=0;
  for(auto &[r, e, i]: qry){
    cin >> r >> e;
    i = aux++;
  }

  sort(qry.begin(), qry.end());

  vector<iii> ev;

  for(int i=0; i<n; i++){
    auto [x, y, r1] = coord[i];
    for(int j=i+1; j<n; j++){
      if(i == j) continue;
      auto[a, b, r2] = coord[j];

      int ll =0, rr = 1e9+5;
      int tmp =0;
      while(ll <= rr){
        int mid = (ll + rr)>>1;
        if(check(x, y, a, b, r1+mid, r2+mid)){
          tmp = mid;
          rr = mid-1;
        }
        else ll = mid+1;
      }
      ev.emplace_back(tmp, i, j);
    }
  }

  sort(ev.begin(), ev.end());

  vector<vector<bool> > ans(m, vector<bool>(4, true));
  int id=0;

  for(auto &[r, e, j] : qry){
    while(id < ev.size() && get<0>(ev[id]) <= r){
      merge(get<1>(ev[id]), get<2>(ev[id]));
      id++;
    }
    r = 2*r;
    for(int i=0; i<n; i++){
      int c = dsfind(i);

      if(esq[c]-r < 0 && dir[c]+r > w){
        if(e == 1 || e == 2) ans[j][3] = ans[j][2] = false;
        else ans[j][0] = ans[j][1] = false;
      }
      if(up[c]+r > h && down[c]-r < 0){
        if(e == 1 || e == 4) ans[j][1] = ans[j][2] = false;
        else ans[j][0] = ans[j][3] = false;
      }

      if(esq[c]-r < 0 && down[c] - r < 0) ans[j][0] = false;
      if(dir[c]+r > w && down[c]-r < 0 ) ans[j][1] = false;
      if(dir[c]+r > w && up[c]+r > h) ans[j][2] = false;
      if(esq[c]-r < 0 && up[c]+r > h) ans[j][3] = false;
    }

    if(!ans[j][e-1]){
      ans[j] = {0, 0, 0, 0};
      ans[j][e-1] = true;
    }
  }

  for(int i=0; i<m; i++){
    for(int j=0; j<4; j++) if(ans[i][j]) cout << j+1;
    cout << '\n';
  }

 
  return 0;
}

Compilation message

park.cpp: In function 'int32_t main()':
park.cpp:99:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     while(id < ev.size() && get<0>(ev[id]) <= r){
      |           ~~~^~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 49836 KB Output is correct
2 Correct 591 ms 49796 KB Output is correct
3 Correct 570 ms 49792 KB Output is correct
4 Correct 604 ms 49844 KB Output is correct
5 Correct 565 ms 49776 KB Output is correct
6 Correct 559 ms 49772 KB Output is correct
7 Correct 535 ms 49916 KB Output is correct
8 Correct 535 ms 49792 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 10572 KB Output is correct
2 Correct 200 ms 11572 KB Output is correct
3 Correct 149 ms 11592 KB Output is correct
4 Correct 161 ms 11608 KB Output is correct
5 Correct 145 ms 11596 KB Output is correct
6 Correct 171 ms 11536 KB Output is correct
7 Correct 68 ms 11212 KB Output is correct
8 Correct 63 ms 11160 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 49836 KB Output is correct
2 Correct 591 ms 49796 KB Output is correct
3 Correct 570 ms 49792 KB Output is correct
4 Correct 604 ms 49844 KB Output is correct
5 Correct 565 ms 49776 KB Output is correct
6 Correct 559 ms 49772 KB Output is correct
7 Correct 535 ms 49916 KB Output is correct
8 Correct 535 ms 49792 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 131 ms 10572 KB Output is correct
12 Correct 200 ms 11572 KB Output is correct
13 Correct 149 ms 11592 KB Output is correct
14 Correct 161 ms 11608 KB Output is correct
15 Correct 145 ms 11596 KB Output is correct
16 Correct 171 ms 11536 KB Output is correct
17 Correct 68 ms 11212 KB Output is correct
18 Correct 63 ms 11160 KB Output is correct
19 Correct 1843 ms 58088 KB Output is correct
20 Correct 1813 ms 58104 KB Output is correct
21 Correct 1635 ms 58212 KB Output is correct
22 Correct 2147 ms 58124 KB Output is correct
23 Correct 1862 ms 58088 KB Output is correct
24 Correct 1659 ms 58304 KB Output is correct