oj.uz

Submission #113350

# Submission time Handle Problem Language Result Execution time Memory
113350 2019-05-25T06:43:18 Z ckodser Park (BOI16_park) C++14
100 / 100
 886 ms 18296 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];
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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 17664 KB Output is correct
2 Correct 345 ms 17700 KB Output is correct
3 Correct 311 ms 17784 KB Output is correct
4 Correct 470 ms 17804 KB Output is correct
5 Correct 342 ms 17664 KB Output is correct
6 Correct 367 ms 17784 KB Output is correct
7 Correct 251 ms 17912 KB Output is correct
8 Correct 222 ms 17784 KB Output is correct
9 Correct 14 ms 17664 KB Output is correct
10 Correct 15 ms 17664 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 18108 KB Output is correct
2 Correct 168 ms 18024 KB Output is correct
3 Correct 185 ms 18028 KB Output is correct
4 Correct 169 ms 18040 KB Output is correct
5 Correct 172 ms 18296 KB Output is correct
6 Correct 170 ms 18040 KB Output is correct
7 Correct 172 ms 18012 KB Output is correct
8 Correct 165 ms 17924 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 17664 KB Output is correct
2 Correct 345 ms 17700 KB Output is correct
3 Correct 311 ms 17784 KB Output is correct
4 Correct 470 ms 17804 KB Output is correct
5 Correct 342 ms 17664 KB Output is correct
6 Correct 367 ms 17784 KB Output is correct
7 Correct 251 ms 17912 KB Output is correct
8 Correct 222 ms 17784 KB Output is correct
9 Correct 14 ms 17664 KB Output is correct
10 Correct 15 ms 17664 KB Output is correct
11 Correct 190 ms 18108 KB Output is correct
12 Correct 168 ms 18024 KB Output is correct
13 Correct 185 ms 18028 KB Output is correct
14 Correct 169 ms 18040 KB Output is correct
15 Correct 172 ms 18296 KB Output is correct
16 Correct 170 ms 18040 KB Output is correct
17 Correct 172 ms 18012 KB Output is correct
18 Correct 165 ms 17924 KB Output is correct
19 Correct 450 ms 18112 KB Output is correct
20 Correct 537 ms 18072 KB Output is correct
21 Correct 477 ms 18148 KB Output is correct
22 Correct 454 ms 18048 KB Output is correct
23 Correct 886 ms 17964 KB Output is correct
24 Correct 356 ms 18108 KB Output is correct