제출 #1098788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098788		Bananabread	Park (BOI16_park)	C++17	100 / 100	349 ms	133036 KiB

park

#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname ""
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
struct pot{
    ll x,y,r;
} arr[2001];
ll ans[100001];
ll par[3001];
ll sz[3001];
ll find_par(ll x){
    return (x==par[x]? x: par[x]=find_par(par[x]));
}
void uni(ll a,ll b){
    a=find_par(a);
    b=find_par(b);
    if(a!=b){
        if(sz[a]<sz[b]) swap(a,b);
        sz[a]+=sz[b];
        par[b]=a;
    }
}
vector<array<ll,4>> sweep;
ll w,h,n,m;
ll dist(pot a,pot b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))-a.r-b.r;
}
bool check(ll st,ll ed){
    if(st>ed) swap(st,ed);
    if(st==ed) return 1;
    if(st==1){
        if(ed==2){
            if(find_par(n+1)==find_par(n+3)) return 0;
            if(find_par(n+2)==find_par(n+3)) return 0;
            if(find_par(n+4)==find_par(n+3)) return 0;
        }
        if(ed==3){
            if(find_par(n+1)==find_par(n+2)) return 0;
            if(find_par(n+1)==find_par(n+3)) return 0;
            if(find_par(n+4)==find_par(n+3)) return 0;
            if(find_par(n+4)==find_par(n+2)) return 0;
        }
        if(ed==4){
            if(find_par(n+1)==find_par(n+4)) return 0;
            if(find_par(n+2)==find_par(n+4)) return 0;
            if(find_par(n+4)==find_par(n+3)) return 0;
        }
    }
    else if(st==2){
        if(ed==3){
            if(find_par(n+1)==find_par(n+2)) return 0;
            if(find_par(n+2)==find_par(n+4)) return 0;
            if(find_par(n+2)==find_par(n+3)) return 0;
        }
        if(ed==4){
            if(find_par(n+1)==find_par(n+3)) return 0;
            if(find_par(n+2)==find_par(n+3)) return 0;
            if(find_par(n+1)==find_par(n+4)) return 0;
            if(find_par(n+4)==find_par(n+2)) return 0;
        }
    }
    else{
        if(find_par(n+1)==find_par(n+3)) return 0;
        if(find_par(n+2)==find_par(n+1)) return 0;
        if(find_par(n+4)==find_par(n+1)) return 0;
    }
    return 1;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n>>m>>w>>h;
    for(int i=1;i<=n;i++){
        ll a,b,r;
        cin>>a>>b>>r;
        arr[i]={a,b,r};
        sweep.push_back({h-b-r,1,i,n+1});
        sweep.push_back({b-r,1,i,n+3});
        sweep.push_back({w-a-r,1,i,n+2});
        sweep.push_back({a-r,1,i,n+4});
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            sweep.push_back({dist(arr[i],arr[j]),1,i,j});
        }
    }
    for(int i=1;i<=n+4;i++){
        sz[i]=1;
        par[i]=i;
    }
    for(int i=1;i<=m;i++){
        ll r,st;
        cin>>r>>st;
        sweep.push_back({2*r,0,st,i});
    }
    sort(sweep.begin(),sweep.end());
    for(auto i:sweep){
        ll type=i[1],u=i[2],v=i[3];
        if(type){
            uni(u,v);
            //cout<<u<<' '<<v<<' '<<i[0]<<ntr;
        }
        else{
            //cout<<v<<ntr;
            for(int i=1;i<=4;i++){
                if(check(u,i)) ans[v]*=10,ans[v]+=i;
            }
        }
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<ntr;
    }
}

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