Submission #386427

#	Time	Username	Problem	Language	Result	Execution time	Memory
386427		L_lawliet27	Park (BOI16_park)	C++17	100 / 100	380 ms	50144 KiB

park

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define pb push_back
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define int long long
#define sz(x) (ll)(x.size())
using namespace std;
using namespace __gnu_pbds;
 
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}

const int mod = 1e9+7;

int expo_pow(int x,int y){
 if(y == 0) return 1;
  y=y%(mod-1);
  x%=mod;
  if(y==0) y=mod-1;
  int res=1;
  while(y){
    if(y&1) res=(res*x)%mod;
    x=(x*x)%mod;
    y>>=1; 
  }
  return res;
}

ll add()
{
    return 0;
}

template <typename T, typename... Types>
T add(T var1, Types... var2){
    return (((((ll)(var1)) % mod + (ll)(add(var2...))) % mod) + mod) % mod;
}

ll mul(){
    return 1;
}

template <typename T, typename... Types>
T mul(T var1, Types... var2){
    return (((ll)(var1)) % mod * (ll)(mul(var2...))) % mod;
}

const int mx = 2020;
int par[mx];
vector<pair<pii,int>> a;


double dist(pii x,pii y) {
  return sqrt((x.f - y.f)*(x.f-y.f) + (x.s-y.s)*(x.s-y.s));
}

int find_(int x) {
  if (par[x] == x) return x;
  return par[x] = find_(par[x]);
}

const int inf = 1e18;
void solve(){
  int n,m;
  int w,h;
  cin >> n >> m;
  cin >> w >> h;

  for (int i = 0; i < mx; ++i) par[i] = i;

  int ans[4][4];
  for (int i = 0; i < 4; ++i) for (int j = 0; j <4; ++j) ans[i][j] = inf;
  a.resize(n);

  for (int i = 0; i < n ;++i) {
    cin >> a[i].f.f >> a[i].f.s >> a[i].s;
  }

  vector<pair<int,pii>> edges;

  for (int i = 0; i < n; ++i) {
    for (int j = i+1; j < n ;++j) {
      int len = (dist(a[i].f,a[j].f) - a[i].s - a[j].s)/2;
      edges.pb({len,{i,j}});
    }
    edges.pb({(a[i].f.f - a[i].s)/2,{i,n}});
    edges.pb({(a[i].f.s - a[i].s)/2,{i,n+1}});
    edges.pb({(w - a[i].f.f - a[i].s)/2,{i,n+2}});
    edges.pb({(h - a[i].f.s - a[i].s)/2,{i,n+3}});
  
  }

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

  for (auto u:edges) {
    int x = find_(u.s.f);
    int y = find_(u.s.s);
    if (x == y) continue;
    par[x] = y;

    for (int i = 0; i < 4; ++i) {
      int j = (i+1)%4;
      if (find_(n+i) == find_(n+j)) {
        for (int k = 0; k < 4; ++k) {
          if (i == k) continue;
          ans[i][k] = ans[k][i] = min(ans[i][k],u.f);
        }
      }
    }

    if (find_(n) == find_(n+2)) {
      ans[2][0] = ans[0][2] = min(ans[2][0],u.f);
      ans[2][1] = ans[1][2] = min(ans[1][2],u.f);
      ans[3][0] = ans[0][3] = min(ans[3][0],u.f);
      ans[3][1] = ans[1][3] = min(ans[1][3],u.f);
    }

    if (find_(n+1) == find_(n+3)) {
      ans[0][1] = ans[1][0] = min(ans[0][1],u.f);
      ans[0][2] = ans[2][0] = min(ans[0][2],u.f);
      ans[3][1] = ans[1][3] = min(ans[3][1],u.f);
      ans[3][2] = ans[2][3] = min(ans[3][2],u.f);
    }

  }
  //for (int i = 0; i < 

  for (int i  =0; i < m; ++i) {
    int r,e;
    cin >> r >> e;
    e--;
    for (int j = 0; j <4; ++j) {
      if (ans[e][j] >=r) cout << j+1;
    }
    cout << "\n";
  }

}


signed main(){
  fast;
  int test = 1;
  int i=1;
  while(test--){
    solve();
  }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:157:7: warning: unused variable 'i' [-Wunused-variable]
  157 |   int i=1;
      |       ^

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