제출 #724780

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
724780		vjudge1	Park (BOI16_park)	C++17	100 / 100	2147 ms	58304 KiB

park

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42