oj.uz

Submission #113337

# Submission time Handle Problem Language Result Execution time Memory
113337 2019-05-25T06:16:53 Z ckodser Park (BOI16_park) C++14
31 / 100
 2500 ms 135800 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2538 ms 135800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 38780 KB Output is correct
2 Correct 275 ms 38904 KB Output is correct
3 Correct 270 ms 38904 KB Output is correct
4 Correct 263 ms 39044 KB Output is correct
5 Correct 259 ms 38904 KB Output is correct
6 Correct 241 ms 38904 KB Output is correct
7 Correct 186 ms 36472 KB Output is correct
8 Correct 189 ms 36472 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2538 ms 135800 KB Time limit exceeded
2 Halted 0 ms 0 KB -