oj.uz

Submission #74075

# Submission time Handle Problem Language Result Execution time Memory
74075 2018-08-30T03:10:22 Z tmwilliamlin168 Park (BOI16_park) C++14
100 / 100
 835 ms 39548 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pli pair<ll, int>
#define fi first
#define se second

const int mxN=2e3, mxM=1e5;
int n, m;
ll w, h, x[mxN], y[mxN], r[mxN], sr[mxN][mxN], ans[4][4], dist[mxN];
bool vis[mxN];

ll c1(int a) {
	ll b=LLONG_MAX;
	memset(dist, 0x3F, 8*n);
	for(int i=0; i<n; ++i) {
		dist[i]=min(x[i]-r[i], dist[i]);
		dist[i]=min(h-y[i]-r[i], dist[i]);
		if(a==0)
			dist[i]=min(w-x[i]-r[i], dist[i]);
	}
	memset(vis, 0, n);
	for(int it=0; it<n; ++it) {
		int mi=-1;
		for(int i=0; i<n; ++i)
			if(!vis[i]&&(mi==-1||dist[i]<dist[mi]))
				mi=i;
		vis[mi]=1;
		for(int i=0; i<n; ++i)
			if(!vis[i])
				dist[i]=min(max(sr[i][mi], dist[mi]), dist[i]);
		b=min(max(y[mi]-r[mi], dist[mi]), b);
		if(a==1)
			b=min(max(w-x[mi]-r[mi], dist[mi]), b);
	}
	return b;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> w >> h;
	for(int i=0; i<n; ++i)
		cin >> x[i] >> y[i] >> r[i];
	for(int i=0; i<n; ++i) {
		for(int j=i+1; j<n; ++j) {
			ll lb=1, rb=1e9;
			while(lb<=rb) {
				ll mb=(lb+rb)/2, a=mb+r[i]+r[j], dx=x[i]-x[j], dy=y[i]-y[j];
				if(a*a<=dx*dx+dy*dy)
					lb=mb+1;
				else
					rb=mb-1;
			}
			sr[i][j]=sr[j][i]=rb;
		}
	}
	for(int i=0, j=0, k=1; i<4; ++i, j^=2) {
		ans[i][i]=LLONG_MAX;
		ans[j][j^k]=ans[j^k][j]=c1(0);
		for(int l=0; l<n; ++l)
			y[l]=h-y[l];
		if(i==1) {
			ans[0][2]=ans[2][0]=c1(1);
			swap(w, h);
			for(int l=0; l<n; ++l)
				swap(x[l], y[l]);
			k^=2;
		} else if(i==0)
			ans[1][3]=ans[3][1]=c1(1);
	}
	while(m--) {
		int ri, ei;
		cin >> ri >> ei, --ei;
		for(int i=0; i<4; ++i)
			if(2*ri<=ans[ei][i])
				cout << i+1;
		cout << "\n";
	}
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 31952 KB Output is correct
2 Correct 776 ms 32052 KB Output is correct
3 Correct 762 ms 32268 KB Output is correct
4 Correct 762 ms 32268 KB Output is correct
5 Correct 812 ms 32356 KB Output is correct
6 Correct 730 ms 32404 KB Output is correct
7 Correct 604 ms 32560 KB Output is correct
8 Correct 566 ms 32560 KB Output is correct
9 Correct 2 ms 32560 KB Output is correct
10 Correct 2 ms 32560 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 32560 KB Output is correct
2 Correct 46 ms 32560 KB Output is correct
3 Correct 42 ms 32560 KB Output is correct
4 Correct 46 ms 32560 KB Output is correct
5 Correct 47 ms 32560 KB Output is correct
6 Correct 48 ms 32560 KB Output is correct
7 Correct 37 ms 32560 KB Output is correct
8 Correct 37 ms 32560 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 31952 KB Output is correct
2 Correct 776 ms 32052 KB Output is correct
3 Correct 762 ms 32268 KB Output is correct
4 Correct 762 ms 32268 KB Output is correct
5 Correct 812 ms 32356 KB Output is correct
6 Correct 730 ms 32404 KB Output is correct
7 Correct 604 ms 32560 KB Output is correct
8 Correct 566 ms 32560 KB Output is correct
9 Correct 2 ms 32560 KB Output is correct
10 Correct 2 ms 32560 KB Output is correct
11 Correct 51 ms 32560 KB Output is correct
12 Correct 46 ms 32560 KB Output is correct
13 Correct 42 ms 32560 KB Output is correct
14 Correct 46 ms 32560 KB Output is correct
15 Correct 47 ms 32560 KB Output is correct
16 Correct 48 ms 32560 KB Output is correct
17 Correct 37 ms 32560 KB Output is correct
18 Correct 37 ms 32560 KB Output is correct
19 Correct 835 ms 34412 KB Output is correct
20 Correct 825 ms 35336 KB Output is correct
21 Correct 802 ms 36516 KB Output is correct
22 Correct 825 ms 37304 KB Output is correct
23 Correct 817 ms 38380 KB Output is correct
24 Correct 665 ms 39548 KB Output is correct