oj.uz

Submission #145065

# Submission time Handle Problem Language Result Execution time Memory
145065 2019-08-18T16:39:00 Z mosesmayer Park (BOI16_park) C++17
100 / 100
 804 ms 33596 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<pii, int> iii;

const LL LINF = 1e18;
const int mxsz = 2e3 + 10;
int n, m;
int w, h;

struct Circ{
	int x, y, r;
	Circ(){}
	Circ(int x, int y, int r): x(x), y(y), r(r) {}
} cr[mxsz];

istream& operator>> (istream& is, Circ &c) {
	is >> c.x >> c.y >> c.r;
	return is;
}

LL d[mxsz][mxsz];

void read(){
	cin >> n >> m >> w >> h;
	for (int i = 1; i <= n; i++){
		cin >> cr[i];
	}
}

LL dist[mxsz], M[5][5], R[5][5]; // min, resDijk
bool vis[mxsz];
int N;
LL dijkstra(int st, int ed){
	fill(dist, dist+N+1, LINF);
	fill(vis+1, vis+N+1, 0);

	dist[st] = 0;
	for (int run = 1; run <= N; run++){
		int mnid = 0;
		for (int i = 1; i <= N; i++){
			if (vis[i]) continue;
			if (!mnid || dist[mnid] > dist[i])
				mnid = i;
		}
	//	cout << mnid << ": ";
		vis[mnid] = 1;
		for (int i = 1; i <= N; i++){
			if (!vis[i])
				dist[i] = min(dist[i], max(dist[mnid], d[i][mnid]));
		}
	//	for (int i = 1; i <= N; i++) cout << dist[i] << " \n"[i==N];
	}
//	cout << dist[ed] << '\n';
	return dist[ed];
}

inline LL binsearch_diam(int i, int j){
	// find max diam fit between two crles
	LL lo = 0, hi = 1e9, md, res = 0;
	LL tr = cr[i].r + cr[j].r;
	LL dx = cr[j].x - cr[i].x, dy = cr[j].y - cr[i].y;
	LL sqd = dx * dx + dy * dy;
	while (lo <= hi){
		md = (lo + hi) >> 1;
		if ((md + tr) * (md + tr) <= sqd){
			res = md; lo = md + 1;
		} else hi = md - 1;
	}
	return res;
}
void calc(){
	for (int i = 1; i <= n; i++) for (int j = i+1; j <= n; j++)
		d[i][j] = d[j][i] = binsearch_diam(i, j);
	//for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
	//	cout << d[i][j] << " \n"[j==n]; // DONE
	//1l2r3d4u
	for (int i = 1; i <= n; i++){
		d[i][n+1] = d[n+1][i] = cr[i].x - cr[i].r;
		d[i][n+2] = d[n+2][i] = w - cr[i].x - cr[i].r;
		d[i][n+3] = d[n+3][i] = cr[i].y - cr[i].r;
		d[i][n+4] = d[n+4][i] = h - cr[i].y - cr[i].r;
	}
	for (int i = 1; i <= N; i++) d[i][i] = LINF;
	N = n+4;
	for (int i = 1; i <= 4; i++) for (int j = i+1; j <= 4; j++)
		d[n+i][n+j] = d[n+j][n+i] = LINF;
	for (int i = 1; i <= 4; i++)
		for (int j = i+1; j <= 4; j++)
			R[i][j] = R[j][i] = dijkstra(n+i, n+j);
	for (int i = 1; i <= 4; i++)
		M[i][i] = LINF;
	M[1][2] = min(R[3][4], min(R[1][3], R[2][3]));
	M[1][3] = min(min(R[1][3], R[2][4]), min(R[1][2], R[3][4]));
	M[1][4] = min(R[1][2], min(R[1][3], R[1][4]));
	M[2][3] = min(R[1][2], min(R[2][3], R[2][4]));
	M[2][4] = min(min(R[2][3], R[1][4]), min(R[1][2], R[3][4]));
	M[3][4] = min(R[3][4], min(R[1][4], R[2][4]));
	for (int i = 1; i <= 4; i++) for (int j = i+1; j <= 4; j++)
		M[j][i] = M[i][j];
//	for (int i = 1; i <= 4; i++) for (int j = i+1; j <= 4; j++)
//		cout << R[i][j] << " \n"[i+j == 7];
//	for (int i = 1; i <= 4; i++) for (int j = i+1; j <= 4; j++)
//		cout << M[i][j] << " \n"[i+j == 7];
}

void query(LL r, int st){
	for (int i = 1; i <= 4; i++){
		if (r * 2 <= M[i][st]) cout << i;
	}
	cout << '\n';
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	read();
	calc();
	for (int i = 0, r, s; i < m; i++){
		cin >> r >> s;
		query(r, s);
	}
	return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 32248 KB Output is correct
2 Correct 700 ms 32024 KB Output is correct
3 Correct 710 ms 32072 KB Output is correct
4 Correct 689 ms 31912 KB Output is correct
5 Correct 695 ms 32120 KB Output is correct
6 Correct 697 ms 32080 KB Output is correct
7 Correct 569 ms 32120 KB Output is correct
8 Correct 577 ms 32172 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2936 KB Output is correct
2 Correct 45 ms 2808 KB Output is correct
3 Correct 44 ms 2808 KB Output is correct
4 Correct 45 ms 2936 KB Output is correct
5 Correct 44 ms 2936 KB Output is correct
6 Correct 47 ms 2936 KB Output is correct
7 Correct 38 ms 1912 KB Output is correct
8 Correct 38 ms 1812 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 32248 KB Output is correct
2 Correct 700 ms 32024 KB Output is correct
3 Correct 710 ms 32072 KB Output is correct
4 Correct 689 ms 31912 KB Output is correct
5 Correct 695 ms 32120 KB Output is correct
6 Correct 697 ms 32080 KB Output is correct
7 Correct 569 ms 32120 KB Output is correct
8 Correct 577 ms 32172 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 47 ms 2936 KB Output is correct
12 Correct 45 ms 2808 KB Output is correct
13 Correct 44 ms 2808 KB Output is correct
14 Correct 45 ms 2936 KB Output is correct
15 Correct 44 ms 2936 KB Output is correct
16 Correct 47 ms 2936 KB Output is correct
17 Correct 38 ms 1912 KB Output is correct
18 Correct 38 ms 1812 KB Output is correct
19 Correct 759 ms 33356 KB Output is correct
20 Correct 804 ms 33444 KB Output is correct
21 Correct 737 ms 33356 KB Output is correct
22 Correct 710 ms 33440 KB Output is correct
23 Correct 727 ms 33596 KB Output is correct
24 Correct 640 ms 33500 KB Output is correct