Submission #113350

#	Time	Username	Problem	Language	Result	Execution time	Memory
113350		ckodser	Park (BOI16_park)	C++14	100 / 100	886 ms	18296 KiB

park

#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=2100;
const ll inf=1e9+900;
const ld eps=1e-7;

ll ger[maxn][maxn];
ll smin[4][maxn];
bool vis[maxn];
ll d[maxn];



void find_smin(ll a,ll b,ll n){
    fill(smin[b],smin[b]+maxn,inf);
    memset(vis,0,sizeof vis);
    fill(d,d+maxn,inf);
    
    
    d[a]=0;
    for(ll iii=0;iii<n;iii++){	
	pii e=mp(inf+1,inf);
	for(ll i=0;i<n;i++){
	    if(!vis[i])e=min(e,mp(d[i],i));
	}
	ll v=e.S;
	ll w=e.F;
	vis[v]=1;
	smin[b][v]=w;
	for(ll i=0;i<n;i++){
	    d[i]=min(d[i],max(w,ger[i][v]));
	}
    }
}


ll x[maxn];
ll y[maxn];
ll r[maxn];
ll minn[5][5];


inline long long tav2(long long a){
    return a*a;
}
inline ll fas(ll a,ll b){
    return (sqrt(tav2(x[a]-x[b])+tav2(y[a]-y[b]))-r[a]-r[b])/2+eps;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n,m,w,h;
    cin>>n>>m>>w>>h;
    for(ll i=0;i<n;i++){
	cin>>x[i]>>y[i]>>r[i];
    }
    memset(ger,63,sizeof ger);
    for(ll i=0;i<n;i++){
	for(ll j=0;j<n;j++){
	    if(i!=j){
		ger[i][j]=fas(i,j);
	    }
	}
	ger[i][n+1]=(x[i]-r[i])/2;
	ger[i][n+0]=(y[i]-r[i])/2;
	ger[i][n+3]=(w-x[i]-r[i])/2;
	ger[i][n+2]=(h-y[i]-r[i])/2;
    }
    for(ll i=0;i<n;i++){
	for(ll j=n;j<n+4;j++){
	    ger[j][i]=ger[i][j];
	}
    }
    for(ll i=0;i<4;i++){
	find_smin(n+i,i,n+4);/*
	cout<<i<<"::";
	for(ll j=n;j<n+4;j++){
	    cout<<smin[i][j]<<' ';
	}
	cout<<endl;*/
    }
    for(ll i=1;i<=4;i++){
	minn[i][i]=inf;
    }
    minn[1][2]=min(min(smin[0][n+2],smin[0][n+3]),smin[0][n+1]);
    minn[1][3]=min(min(min(smin[0][n+2],smin[2][n+3]),smin[0][n+1]),smin[1][n+3]);
    minn[1][4]=min(min(smin[1][n+3],smin[1][n+2]),smin[0][n+1]);

    minn[2][3]=min(min(smin[1][n+3],smin[0][n+3]),smin[2][n+3]);
    minn[2][4]=min(min(min(smin[0][n+2],smin[2][n+1]),smin[0][n+3]),smin[1][n+3]);;
    
    minn[3][4]=min(min(smin[0][n+2],smin[1][n+2]),smin[2][n+3]);




    for(ll i=1;i<=4;i++){
	for(ll j=i+1;j<=4;j++){
	    minn[j][i]=minn[i][j];
	}
    }
    
    for(ll i=0;i<m;i++){
	ll r,e;
	cin>>r>>e;
	for(ll i=1;i<=4;i++){
	    if(r<=minn[e][i]){
		cout<<i;
	    }
	}
	cout<<endl;
    }
}

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