oj.uz

답안 #1018026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018026 2024-07-09T13:01:01 Z m5588ohammed Park (BOI16_park) C++14
0 / 100
 642 ms 1872 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
int UP,DOWN,RIGHT,LEFT,mx[5][5];
int n,m,t,v;
int parent[2005];
vector <array<int,3>> rad;
void make_set(int i){
    parent[i]=i;
    return;
}
int find(int a){
    if(parent[a]==a) return a;
    else return parent[a]=find(parent[a]);
}
void merge(int a,int b){
    a=find(a),b=find(b);
    parent[b]=a;
    return;
}
bool UP_DOWN(){ return find(UP)==find(DOWN);}
bool UP_RIGHT(){ return find(UP)==find(RIGHT);}
bool UP_LEFT(){ return find(UP)==find(LEFT);}
bool DOWN_LEFT(){ return find(DOWN)==find(LEFT);}
bool DOWN_RIGHT(){ return find(DOWN)==find(RIGHT);}
bool LEFT_RIGHT(){ return find(LEFT)==find(RIGHT);}

void make(int k){
    for(int i=0;i<=LEFT;i++) make_set(i);
    for(int i=0;i<t;i++){
        auto [x1,y1,r1]=rad[i];
        for(int j=i+1;j<t;j++){
            auto [x2,y2,r2]=rad[j];
            if((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<=(r1+r2+k)*(r1+r2+k)) merge(i,j);   
        }
        if(x1-r1-k<=0) merge(LEFT,i);
        if(x1+r1+k>=n) merge(RIGHT,i);
        if(y1-r1-k<=0) merge(UP,i);
        if(y1+r1+k>=m) merge(DOWN,i);
    }
}
int solve(int st,int en){
    int l=0,r=1e9,ans=0;
    while(l<=r){
        int k=(l+r)/2;
        make(k);
        if(st==1&&en==4){
            if(LEFT_RIGHT()==1||UP_LEFT()==1||DOWN_LEFT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
        if(st==2&&en==4){
            if(LEFT_RIGHT()==1||UP_DOWN()==1||UP_LEFT()==1||DOWN_RIGHT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
        if(st==3&&en==4){
            if(UP_DOWN()==1||UP_LEFT()==1||UP_RIGHT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
        if(st==1&&en==2){
            if(DOWN_LEFT()==1||UP_DOWN()==1||DOWN_RIGHT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
        if(st==1&&en==3){
            if(LEFT_RIGHT()==1||UP_DOWN()==1||DOWN_LEFT()==1||UP_RIGHT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
        if(st==2&&en==3){
            if(LEFT_RIGHT()==1||DOWN_RIGHT()==1||UP_RIGHT()==1) r=k-1;
            else{ans=k;l=k+1;}
        }
    }
    return ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>t>>v>>n>>m;
    for(int i=0;i<t;i++){
        int x,y,r;
        cin>>x>>y>>r;
        rad.push_back({x,y,r});
    }
    UP=t+1,DOWN=t+2,RIGHT=t+3,LEFT=t+4;
    for(int d1=1;d1<=4;d1++) for(int d2=d1+1;d2<=4;d2++) mx[d1][d2]=solve(d1,d2);
    // cout<<mx[1][2]<<endl;
    // cout<<mx[1][3]<<endl;
    // cout<<mx[1][4]<<endl;
    //cout<<mx[2][3]<<endl;
    // cout<<mx[2][4]<<endl;
    // cout<<mx[3][4]<<endl;
    while(v--){
        int st,r;
        cin>>r>>st;
        vector <int> ans;
        ans.push_back(st);
        if(mx[min(st,1ll)][max(st,1ll)]>=r*2) ans.push_back(1);
        if(mx[min(st,2ll)][max(st,2ll)]>=r*2) ans.push_back(2);
        if(mx[min(st,3ll)][max(st,3ll)]>=r*2) ans.push_back(3);
        if(mx[min(st,4ll)][max(st,4ll)]>=r*2) ans.push_back(4);
        sort(ans.begin(),ans.end());
        for(int i:ans) cout<<i;
        cout<<endl;
    }

    return 0;
}

Compilation message

park.cpp: In function 'void make(long long int)':
park.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |         auto [x1,y1,r1]=rad[i];
      |              ^
park.cpp:34:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |             auto [x2,y2,r2]=rad[j];
      |                  ^

Subtask #1
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 613 ms 604 KB Output is correct
2 Incorrect 642 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 1872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 613 ms 604 KB Output is correct
2 Incorrect 642 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -