Submission #113337

#	Time	Username	Problem	Language	Result	Execution time	Memory
113337		ckodser	Park (BOI16_park)	C++14	31 / 100	2538 ms	135800 KiB

park

#include<bits/stdc++.h>

#define ll long long
#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];

void find_smin(ll a,ll b,ll n){
    fill(smin[b],smin[b]+maxn,inf);
    set<pii> st;
    st.insert(mp(0,a));
    while(st.size()){
	pii e=(*st.begin());
	st.erase(e);
	ll v=e.S;
	ll w=e.F;
	if(smin[b][v]>w){
	    smin[b][v]=w;
	    for(ll i=0;i<n;i++){
		if(i!=v){
		    st.insert(mp(max(w,ger[i][v]),i));
		}
	    }
	}
    }
}



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


inline ll tav2(ll a){
    return a*a;
}
inline ld fas(ll a,ll b){
    return sqrt(tav2(x[a]-x[b])+tav2(y[a]-y[b]));
}

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)-r[i]-r[j])/2+eps;
	    }
	}
	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<n+4;i++){
	for(ll j=0;j<n+4;j++){
	    if(ger[i][j]>100){
		cout<<"I ";
	    }else{
		cout<<ger[i][j]<<' ';
	    }
	}
	cout<<endl;
    }*/
    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: 0 / 27
• Subtask 2: 31 / 31
• Subtask 3: 0 / 42