oj.uz

Submission #113345

# Submission time Handle Problem Language Result Execution time Memory
113345 2019-05-25T06:38:36 Z ckodser Park (BOI16_park) C++14
31 / 100
 2500 ms 103000 KB 
#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];


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));
		}
	    }
	}
    }
}


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
0 / 27.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 19972 KB Output is correct
2 Correct 221 ms 19960 KB Output is correct
3 Correct 228 ms 19960 KB Output is correct
4 Correct 222 ms 19988 KB Output is correct
5 Correct 225 ms 19952 KB Output is correct
6 Correct 206 ms 19832 KB Output is correct
7 Correct 164 ms 17912 KB Output is correct
8 Correct 165 ms 17912 KB Output is correct

Subtask #3
0 / 42.0

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