Submission #1193869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193869		irmuun	Park (BOI16_park)	C++20	100 / 100	284 ms	26004 KiB

park

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct dsu{
    int n;
    vector<int>sz,par;
    dsu(int n):n(n){
        sz.resize(n);
        par.resize(n);
        fill(all(sz),1);
        iota(all(par),0);
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    bool same(int x,int y){
        x=find(x);
        y=find(y);
        return x==y;
    }
    void merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x!=y){
            if(sz[x]<sz[y]) swap(x,y);
            par[y]=x;
            sz[x]+=x;
        }
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    auto dist=[&](int x1,int y1,int x2,int y2,int r1,int r2){
        return sqrt(1ll*(x1-x2)*(x1-x2)+1ll*(y1-y2)*(y1-y2))-r1-r2;
    };
    int n,m;
    cin>>n>>m;
    int w,h;
    cin>>w>>h;
    int x[n],y[n],r[n];
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i]>>r[i];
    }
    int E[m],R[m];
    for(int i=0;i<m;i++){
        cin>>R[i]>>E[i];
        R[i]*=2;
        E[i]--;
    }
    vector<array<int,3>>edge;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int d=(int)dist(x[i],y[i],x[j],y[j],r[i],r[j]);
            edge.pb({d,i+4,j+4});
        }
        edge.pb({x[i]-r[i],0,i+4});
        edge.pb({w-x[i]-r[i],2,i+4});
        edge.pb({y[i]-r[i],1,i+4});
        edge.pb({h-y[i]-r[i],3,i+4});
    }
    sort(all(edge));
    auto mx=vector(4,vector<int>(4,1e9));
    dsu ds(n+4);
    for(int i=0;i<edge.size();i++){
        ds.merge(edge[i][1],edge[i][2]);
        for(int j=0;j<4;j++){
            for(int k=j+1;k<4;k++){
                if(ds.same(j,k)){
                    mx[j][k]=min(mx[j][k],edge[i][0]);
                    mx[k][j]=min(mx[k][j],edge[i][0]);
                }
            }
        }
    }
    auto ans=vector(4,vector<int>(4,1e9));
    ans[0][1]=ans[1][0]=min({mx[1][0],mx[1][3],mx[1][2]});
    ans[1][2]=ans[2][1]=min({mx[2][1],mx[2][0],mx[2][3]});
    ans[2][3]=ans[3][2]=min({mx[3][2],mx[3][1],mx[3][0]});
    ans[3][0]=ans[0][3]=min({mx[0][3],mx[0][2],mx[0][1]});
    ans[0][2]=ans[2][0]=min({mx[0][2],mx[1][3],mx[0][1],mx[2][3]});
    ans[1][3]=ans[3][1]=min({mx[0][2],mx[1][3],mx[1][2],mx[0][3]});
    for(int i=0;i<m;i++){
        for(int j=0;j<4;j++){
            if(ans[E[i]][j]>=R[i]){
                cout<<j+1;
            }
        }
        cout<<"\n";
    }
}

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