Submission #145065

#	Time	Username	Problem	Language	Result	Execution time	Memory
145065		mosesmayer	Park (BOI16_park)	C++17	100 / 100	804 ms	33596 KiB

park

#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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42