Submission #53802

#	Time	Username	Problem	Language	Result	Execution time	Memory
53802		ruhanhabib39	Park (BOI16_park)	C++17	100 / 100	1215 ms	35724 KiB

park

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000;
const int MAXM = 1e5;

int n, m;
long long w, h;

struct Tree {
   long long x, y, r;
};

int par[MAXN + 10];
Tree tree[MAXN + 10];

struct Query {
   long long r;
   int e, i;
   bool operator<(Query q) const {
      if(r == q.r) return i < q.i;
      return r < q.r;
   }
};

Query query[MAXM + 10];
bitset<4> res[MAXM + 10];

struct dat {
   long long r; int i, j;
   bool operator<(dat d) const {
      return make_tuple(r, i, j) < make_tuple(d.r, d.i, d.j);
   }
};

long long sq(long long x) {
   return x*x;
}

bool bad(int i, int j, long long r) {
   if(i >= n && j >= n) return false;
   if(j >= n) swap(i, j);
   if(i >= n) {
      switch(i-n) {
      case 0: return tree[j].y - tree[j].r - 2*r < 0LL;
      case 1: return tree[j].x + tree[j].r + 2*r > w;
      case 2: return tree[j].y + tree[j].r + 2*r > h;
      case 3: return tree[j].x - tree[j].r - 2*r < 0LL;
      default: assert(false);
      }
   } else {
      return sq(tree[i].x - tree[j].x) + sq(tree[i].y - tree[j].y) < sq(tree[i].r + tree[j].r + 2*r);
   }
}

int calc(int i, int j) {
   long long lo = 0, hi = w + h + 10;
   while(lo < hi) {
      long long m = (lo + hi) / 2;
      if(bad(i, j, m)) hi = m;
      else lo = m+1;
   }
   return lo;
}

int find(int i) {
   if(par[i] == -1) return i;
   return par[i] = find(par[i]);
}

void merge(int i, int j) {
   i = find(i); j = find(j);
   if(i == j) return;
   par[i] = j;
}

void work() {
   vector<dat> vec;
   for(int i = 0; i < n+4; i++) {
      for(int j = i+1; j < n+4; j++) {
         vec.push_back(dat{calc(i, j), i, j});
      }
   }
   sort(vec.begin(), vec.end());

   memset(par, -1, sizeof par);
   int vi = -1;
   for(int qi = 0; qi < m; qi++) {
      auto qq = query[qi];
      while(vi+1 < (int)vec.size() && vec[vi+1].r <= qq.r) {
         vi++;
         merge(vec[vi].i, vec[vi].j);
      }

      auto good = [qq](int i, int j) {
         return find(n + (qq.e + i) % 4) != find(n + (qq.e + j) % 4);
      };
      
      res[qq.i][qq.e] = true;
      if(good(0, 3) && good(0, 2) && good(0, 1)) res[qq.i][(qq.e + 1) % 4] = true;
      if(good(0, 3) && good(0, 2) && good(1, 2) && good(1, 3)) res[qq.i][(qq.e + 2) % 4] = true;
      if(good(3, 0) && good(3, 2) && good(3, 1)) res[qq.i][(qq.e + 3) % 4] = true;
   }
}

int main() {
   scanf("%d%d%lld%lld", &n, &m, &w, &h);
   for(int i = 0; i < n; i++) {
      scanf("%lld%lld%lld", &tree[i].x, &tree[i].y, &tree[i].r);
   }
   for(int i = 0; i < m; i++) {
      scanf("%lld%d", &query[i].r, &query[i].e);
      query[i].e--;
      query[i].i = i;
   }
   sort(query, query + m);

   work();
   for(int i = 0; i < m; i++) {
      for(int e = 0; e < 4; e++) {
         if(res[i][e]) printf("%d", e+1);
      }
      printf("\n");
   }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%lld%lld", &n, &m, &w, &h);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:109:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld%lld%lld", &tree[i].x, &tree[i].y, &tree[i].r);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:112:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld%d", &query[i].r, &query[i].e);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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