Submission #724752

#	Time	Username	Problem	Language	Result	Execution time	Memory
724752		vjudge1	Park (BOI16_park)	C++17	0 / 100	177 ms	96764 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)) 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;
  int w, h;
  cin >> n >> m;
  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, r] = coord[i];
    for(int j=0; j<n; j++){
      if(i == j) continue;
      auto [a, b, t] = coord[j];
      pq[i].push({(x-a)*(x-a) + (y-b)*(y-b), t, j});
    }
  }

  vector<vector<int> > ans(m);

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

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

  for(auto [r, e, i] : qry){
    
    for(int j=0; j<n; j++){
      if(pq[j].empty()) continue;
      auto [x, y, r1] = coord[j];
      auto [d, r2, k] = pq[j].top();

      while(check(d, r1 + r, r2 + r)){
        merge(j, k);
        pq[j].pop();
        if(pq[j].empty()) break;
        tie(d, r2, k) = pq[j].top();
      }
    }

    vector<bool> out(4, true);

    r = 2*r; // hora de expandir as paredes, soma R na parede e R no circulo
    for(int j=0; j<n; j++){
      int chief = dsfind(j);

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

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

    if(!out[e-1]) {
      ans[i].push_back(e);
      continue;
    }

    for(int j=0; j<4; j++){
      if(out[j]) ans[i].push_back(j+1);
    }
  }


  for(int i=0; i<m; i++){
    for(auto j : ans[i]) cout << char(j + '0');
    cout << '\n';
  }

  return 0;
}

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