oj.uz

Submission #257186

# Submission time Handle Problem Language Result Execution time Memory
257186 2020-08-03T17:19:29 Z maximath_1 Park (BOI16_park) C++11
100 / 100
 1141 ms 66464 KB 
#include <iostream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <vector>
using namespace std;

#define ld long double
#define ll long long

int n, m;
ll w, h;
struct circle{ll x, y, r;} v[2005];
int par[2020];
vector<pair<pair<int, int>, ld> > edge;

ld dist_to_wall(circle a, int b){
	if(b == 0) return a.y - a.r;
	if(b == 1) return w - a.x - a.r;
	if(b == 2) return h - a.y - a.r;
	if(b == 3) return a.x - a.r;
	return -1.0;
}
ld dist_pt(pair<ll, ll> a, pair<ll, ll> b){
	ll xx = b.first - a.first, yy = b.second - a.second;
	ll sq2 = xx * 1ll * xx + yy * 1ll * yy;
	return (ld)sqrtl(sq2);
}
ld dist_between_circle(circle a, circle b){
	ld dst_rad = dist_pt({a.x, a.y}, {b.x, b.y});
	dst_rad -= (ld)a.r + (ld)b.r;
	return dst_rad;
}

bool cmp(pair<pair<int, int>, ld> a, pair<pair<int, int>, ld> b){
	return a.second < b.second;
}

int find(int x){
	if(x != par[x]) par[x] = find(par[x]);
	return par[x];
}

ld cst[4][4], ans[4][4];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	cin >> w >> h;
	for(int i = 0; i < n; i ++)
		cin >> v[i].x >> v[i].y >> v[i].r;

	for(int i = 0; i < n; i ++){
		for(int j = i + 1; j < n; j ++)
			edge.push_back({{i, j}, dist_between_circle(v[i], v[j])});
		for(int j = n; j < n + 4; j ++)
			edge.push_back({{i, j}, dist_to_wall(v[i], j - n)});
	}

	sort(edge.begin(), edge.end(), cmp);

	for(int i = 0; i < n + 4; i ++) par[i] = i;
	for(int i = 0; i < 4; i ++) for(int j = 0; j < 4; j ++) cst[i][j] = -1.0;

	for(auto i : edge){
		int u = i.first.first, v = i.first.second;
		ld w = i.second;

		int fu = find(u), fv = find(v);
		if(fu != fv) par[fu] = fv;

		for(int a = n; a < n + 4; a ++) for(int b = a + 1; b < n + 4; b ++){ //check walls connected (as if becomes a room)
			if(find(a) == find(b) && cst[a - n][b - n] == -1.0)
				cst[a - n][b - n] = w;
		}
	}

	ans[0][0] = ans[1][1] = ans[2][2] = ans[3][3] = 2e9 + 69;
	ans[0][1] = ans[1][0] = min(cst[0][1], min(cst[0][2], cst[0][3]));
	ans[0][2] = ans[2][0] = min(min(cst[0][3], cst[1][2]), min(cst[0][2], cst[1][3]));
	ans[0][3] = ans[3][0] = min(cst[0][3], min(cst[1][3], cst[2][3]));
	ans[1][2] = ans[2][1] = min(cst[0][1], min(cst[1][3], cst[1][2]));
	ans[1][3] = ans[3][1] = min(min(cst[0][1], cst[2][3]), min(cst[0][2], cst[1][3]));
	ans[2][3] = ans[3][2] = min(cst[2][3], min(cst[1][2], cst[0][2]));

	for(int r, st, i = 0; i < m; i ++){
		cin >> r >> st;
		st --;
		ld dia = 2.0L * r;
		for(int ed = 0; ed < 4; ed ++)
			if(dia <= ans[st][ed]) cout << ed + 1;
		cout << endl;
	}

	return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 915 ms 66236 KB Output is correct
2 Correct 908 ms 66204 KB Output is correct
3 Correct 892 ms 66204 KB Output is correct
4 Correct 892 ms 66292 KB Output is correct
5 Correct 897 ms 66236 KB Output is correct
6 Correct 897 ms 66208 KB Output is correct
7 Correct 854 ms 66204 KB Output is correct
8 Correct 865 ms 66200 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 2596 KB Output is correct
2 Correct 235 ms 2544 KB Output is correct
3 Correct 233 ms 2544 KB Output is correct
4 Correct 237 ms 2544 KB Output is correct
5 Correct 241 ms 2596 KB Output is correct
6 Correct 240 ms 2668 KB Output is correct
7 Correct 233 ms 1884 KB Output is correct
8 Correct 222 ms 1832 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 915 ms 66236 KB Output is correct
2 Correct 908 ms 66204 KB Output is correct
3 Correct 892 ms 66204 KB Output is correct
4 Correct 892 ms 66292 KB Output is correct
5 Correct 897 ms 66236 KB Output is correct
6 Correct 897 ms 66208 KB Output is correct
7 Correct 854 ms 66204 KB Output is correct
8 Correct 865 ms 66200 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 245 ms 2596 KB Output is correct
12 Correct 235 ms 2544 KB Output is correct
13 Correct 233 ms 2544 KB Output is correct
14 Correct 237 ms 2544 KB Output is correct
15 Correct 241 ms 2596 KB Output is correct
16 Correct 240 ms 2668 KB Output is correct
17 Correct 233 ms 1884 KB Output is correct
18 Correct 222 ms 1832 KB Output is correct
19 Correct 1134 ms 66464 KB Output is correct
20 Correct 1114 ms 66460 KB Output is correct
21 Correct 1124 ms 66460 KB Output is correct
22 Correct 1141 ms 66396 KB Output is correct
23 Correct 1126 ms 66464 KB Output is correct
24 Correct 1071 ms 66460 KB Output is correct