Submission #935663

#	Time	Username	Problem	Language	Result	Execution time	Memory
935663		tosivanmak	Park (BOI16_park)	C++17	100 / 100	269 ms	61764 KiB

park

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double

ll n,m;
struct edge{
   ll u,v,dist;
   bool operator<(const edge& e)const{
       return dist<e.dist;
   }
   edge(ll _u, ll _v, ll _dist){
       u=_u,v=_v,dist=_dist;
   }
};
struct popo{
    ll first,second,q;
    bool operator<(const popo& p)const{
        return first<p.first;
    }
};
struct DSU{
    vector<ll>fa,siz;
    void init(ll n){
        fa.resize(n+5);
        siz.resize(n+5);
        for(int i=1;i<=n;i++){
            fa[i]=i,siz[i]=1;
        }
    }
    ll root(ll x){
        return (fa[x]==x ? x : fa[x]=root(fa[x]));
    }
    void unite(ll u, ll v){
        fa[root(u)]=root(v);
    }
}dd;
/*
        n+1: left
        n+2: up
        n+3: right
        n+4: down
    */
bool top_down(){
    return (dd.root(n+2)==dd.root(n+4));
}
bool top_left(){
    return (dd.root(n+2)==dd.root(n+1));
}
bool top_right(){
    return (dd.root(n+2)==dd.root(n+3));
}
bool left_down(){
    return (dd.root(n+1)==dd.root(n+4));
}
bool left_right(){
    return (dd.root(n+1)==dd.root(n+3));
}
bool down_right(){
    return (dd.root(n+4)==dd.root(n+3));
}
ll d(ll r, ll c, ll r2, ll c2, ll a, ll b){
    ld tot=(r-r2)*(r-r2)+(c-c2)*(c-c2);
    tot=sqrt(tot);
    // cout<<tot<<" "<<a+b<<'\n';
    tot-=(a+b);
    tot/=2;
    ll bruh=tot;
    bruh++;
    return bruh;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    ll x[n+5],y[n+5],r[n+5];
    ll w,h;
    cin>>w>>h;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i]>>r[i];
    }
    vector<edge>v;
    /*
        n+1: left
        n+2: up
        n+3: right
        n+4: down
    */
   for(int i=1;i<=n;i++){
       for(int j=i+1;j<=n;j++){
           ll bruh=d(x[i],y[i],x[j],y[j],r[i],r[j]);
        //    cout<<bruh<<" ";
           v.push_back({i,j,bruh});
       }
   }
   for(int i=1;i<=n;i++){
       ld bruh=x[i]-r[i];
       bruh/=2;
       ll store=bruh;
       store++;
       v.push_back({i,n+1,store});
   }
   for(int i=1;i<=n;i++){
       ld bruh=y[i]-r[i];
       bruh/=2;
       ll store=bruh;
       store++;
       v.push_back({i,n+4,store});
   }
   for(int i=1;i<=n;i++){
       ld bruh=h-y[i]-r[i];
       bruh/=2;
       ll store=bruh;
       store++;
       v.push_back({i,n+2,store});
   }
   for(int i=1;i<=n;i++){
       ld bruh=w-x[i]-r[i];
       bruh/=2;
       ll store=bruh;
       store++;
       v.push_back({i,n+3,store});
   }
   dd.init(n+5);
   sort(v.begin(),v.end());
   ll cur=0;
   ll ra[m+5],en[m+5];
   vector<popo>fk;
   for(int i=1;i<=m;i++){
       cin>>ra[i]>>en[i];
       fk.push_back({ra[i],en[i],i});
   }
   sort(fk.begin(),fk.end());
   ll qry[m+5];
   vector<ll>ans[m+5];
   for(int i=1;i<=m;i++){
       ra[i]=fk[i-1].first,en[i]=fk[i-1].second;
       qry[i]=fk[i-1].q;
   }
   for(int i=1;i<=m;i++){
       vector<ll>temp;
       ll rad=ra[i],ent=en[i];
       if(cur==v.size()-1){

       }
       else{
           while(v[cur].dist<=rad){
               dd.unite(v[cur].u,v[cur].v);
               cur++;
               if(cur==v.size()-1){
                   break;
               }
           }
           for(int j=1;j<=4;j++){
               if(j==ent){
                   temp.push_back(j);
               }
               else{
                   if(ent==1){
                       if(dd.root(n+1)==dd.root(n+4)){
                           
                       }
                       else{
                           if(j==2){
                               if(!top_down()&&!down_right()){
                                  temp.push_back(j);
                              }
                           }
                           if(j==3){
                               if(!top_right()&&!top_down()&&!left_right()){
                                   temp.push_back(j);
                               }
                           }
                           if(j==4){
                               if(!left_right()&&!top_left()){
                                   temp.push_back(j);
                               }
                           }
                       }
                   }
                   else if(ent==2){
                       if(down_right()){
                           
                       }
                       else{
                           if(j==1){
                              if(!top_down()&&!left_down()){
                                  temp.push_back(j);
                              }
                           }
                           else if(j==3){
                               if(!top_right()&&!left_right()){
                                   temp.push_back(j);
                               }
                           }
                           else{
                               if(!top_left()&&!top_down()&&!left_right()){
                                   temp.push_back(j);
                               }
                           }
                       }
                   }
                   else if(ent==3){
                       if(top_right()){
                           continue;
                       }
                       if(j==1){
                              if(!left_down()&&!left_right()&&!top_down()){
                                  temp.push_back(j);
                              }
                           }
                           else if(j==2){
                               if(!down_right()&&!left_right()){
                                   temp.push_back(j);
                               }
                           }
                           else{
                               if(!top_left()&&!top_down()){
                                   temp.push_back(j);
                               }
                           }
                   }
                   else{
                       if(top_left()){
                           continue;
                       }
                       if(j==1){
                              if(!left_down()&&!left_right()){
                                  temp.push_back(j);
                              }
                           }
                           else if(j==2){
                               if(!top_down()&&!left_right()&&!down_right()){
                                   temp.push_back(j);
                               }
                           }
                           else{
                               if(!top_right()&&!top_down()){
                                   temp.push_back(j);
                               }
                           }
                   }
               }
           }
       }
       ans[qry[i]]=temp;
   }
   for(int i=1;i<=m;i++){
       for(auto& u: ans[i]){
           cout<<u;
       }
       cout<<'\n';
   }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:144:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |        if(cur==v.size()-1){
      |           ~~~^~~~~~~~~~~~
park.cpp:151:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |                if(cur==v.size()-1){
      |                   ~~~^~~~~~~~~~~~

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