oj.uz

답안 #935663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
935663 2024-02-29T10:51:54 Z tosivanmak Park (BOI16_park) C++17
100 / 100
 269 ms 61764 KB 
#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

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.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 50712 KB Output is correct
2 Correct 196 ms 51636 KB Output is correct
3 Correct 202 ms 50408 KB Output is correct
4 Correct 194 ms 50108 KB Output is correct
5 Correct 193 ms 50880 KB Output is correct
6 Correct 194 ms 51108 KB Output is correct
7 Correct 183 ms 51124 KB Output is correct
8 Correct 182 ms 49852 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 12852 KB Output is correct
2 Correct 49 ms 13388 KB Output is correct
3 Correct 48 ms 12860 KB Output is correct
4 Correct 53 ms 12956 KB Output is correct
5 Correct 57 ms 12784 KB Output is correct
6 Correct 51 ms 13112 KB Output is correct
7 Correct 46 ms 12620 KB Output is correct
8 Correct 42 ms 12476 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 50712 KB Output is correct
2 Correct 196 ms 51636 KB Output is correct
3 Correct 202 ms 50408 KB Output is correct
4 Correct 194 ms 50108 KB Output is correct
5 Correct 193 ms 50880 KB Output is correct
6 Correct 194 ms 51108 KB Output is correct
7 Correct 183 ms 51124 KB Output is correct
8 Correct 182 ms 49852 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 55 ms 12852 KB Output is correct
12 Correct 49 ms 13388 KB Output is correct
13 Correct 48 ms 12860 KB Output is correct
14 Correct 53 ms 12956 KB Output is correct
15 Correct 57 ms 12784 KB Output is correct
16 Correct 51 ms 13112 KB Output is correct
17 Correct 46 ms 12620 KB Output is correct
18 Correct 42 ms 12476 KB Output is correct
19 Correct 269 ms 61260 KB Output is correct
20 Correct 241 ms 60828 KB Output is correct
21 Correct 253 ms 61764 KB Output is correct
22 Correct 253 ms 60832 KB Output is correct
23 Correct 249 ms 60776 KB Output is correct
24 Correct 247 ms 60968 KB Output is correct