Submission #724772

#	Time	Username	Problem	Language	Result	Execution time	Memory
724772		vjudge1	Park (BOI16_park)	C++17	0 / 100	7 ms	468 KiB

park

#include "bits/stdc++.h"

using namespace std;
#define int long long
#define ii pair<int,int>
#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 dis, int r1, int r2){
  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;
}

int getdis(int x, int y, int a, int b){
  return (x-a)*(x-a) + (y-b)*(y-b);
}

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

  int n, m;
  int w, h;
  cin >> n >> m;
  if(m > 1) return 0;
  cin >> w >> h;

  vector<priority_queue<iii, vector<iii>, greater<iii>>> pq(n);

  vector<iii> coord(n);

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

  init(coord);

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

  int e, r;
  cin >> r >> e;

  bool out[4] = {1,1,1,1};
  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) out[3] = out[2] = false;
      else out[0] = out[1] = false;
    }
    if(up[c]+r > h && down[c]-r < 0){
      if(e == 1 || e == 4) out[1] = out[2] = false;
      else out[0] = out[3] = false;
    }

     if(esq[c]-r < 0 && down[c] - r < 0) out[0] = false;
      if(dir[c]+r > w && down[c]-r < 0 ) out[1] = false;
      if(dir[c]+r > w && up[c]+r > h) out[2] = false;
      if(esq[c]-r < 0 && up[c]+r > h) out[3] = false;
  }
  
  if(!out[e-1]){
    cout << e << endl;
    return 0;
  }

  for(int i=0; i<4; i++){
    if(out[i]) cout << i+1;
  }

  cout << endl;

 

  return 0;
}

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42