oj.uz

Submission #1096518

# Submission time Handle Problem Language Result Execution time Memory
1096518 2024-10-04T16:49:59 Z flo Park (BOI16_park) C++14
100 / 100
 456 ms 33736 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define str string
#define pb push_back
#define mp make_pair
#define ll long long
#define lld long double
#define pr pair<int, int>
#define mat vector<vector<ll>>
#define ull unsigned long longt
#define srt(a) sort(a.begin(), a.end())
#define Kimishima cin.tie(0); cout.tie(0);
#define Ayano ios_base::sync_with_stdio(false);
#define dec(u, v) setprecision(v) << fixed << u
#define uni(a) a.resize(unique(a.begin(), a.end())-a.begin())
#define left(a, v) (lower_bound(a.begin(), a.end(), v)-a.begin())
using namespace std;
const int lim = 2e3+4;
ll dp[5][5], l, r, cur, w, h;
struct Edge {ll len; int a, b;}; vector<Edge> e;
struct Cir {ll X, Y, R;} p[lim+5]; int dsu[lim+5];
int find(int v) {
	if (v == dsu[v]) return v;
	return dsu[v] = find(dsu[v]);
}
void unite(int u, int v) {
	u = find(u), v = find(v);
	if (u != v) dsu[v] = u; return;
}
void reset(int n) {
	for (int x = 1; x <= n; x++) dsu[x] = x;
}
ll get(Cir u, Cir v) {
	ll x = u.X-v.X, y = u.Y-v.Y;
	return (ll)(sqrt(x*x+y*y))-u.R-v.R;
}
bool cmp(Edge u, Edge v) {return u.len < v.len;}
void solve() {
	int n, m; cin >> n >> m >> w >> h;
	for (int x = 5; x <= n+4; x++) {
		cin >> p[x].X >> p[x].Y >> p[x].R;
		e.pb({w-p[x].X-p[x].R, 2, x});
		e.pb({h-p[x].Y-p[x].R, 3, x});
		e.pb({p[x].Y-p[x].R, 1, x});
		e.pb({p[x].X-p[x].R, 4, x});
	}
	for (int x = 5; x <= n+4; x++) {
		for (int y = x+1; y <= n+4; y++) {
			e.pb({get(p[x], p[y]), x, y});
		}
	}
	for (int x = 1; x <= 4; x++) dp[x][x] = 2e9;
	sort(e.begin(), e.end(), cmp);
	l = 0, r = min(w, h), cur = -1;
	while (l <= r) {
		ll mid = (l+r)/2; 
		bool check = 1; reset(n+4);
		for (auto x : e) {
			if (x.len >= mid) break;
			unite(x.a, x.b);
		}
		check &= (find(1) != find(2));
		check &= (find(1) != find(3));
		check &= (find(1) != find(4));
		if (check == 0) r = mid-1;
		else l = mid+1, cur = mid;
	}
	dp[1][2] = dp[2][1] = cur;
	l = 0, r = min(w, h), cur = -1;
	while (l <= r) {
		ll mid = (l+r)/2;
		bool check = 1; reset(n+4);
		for (auto x : e) {
			if (x.len >= mid) break;
			unite(x.a, x.b);
		}
		check &= (find(1) != find(3));
		check &= (find(1) != find(4));
		check &= (find(2) != find(3));
		check &= (find(2) != find(4));
		if (check == 0) r = mid-1;
		else l = mid+1, cur = mid;
	}
	dp[1][3] = dp[3][1] = cur;
	l = 0, r = min(w, h), cur = -1;
	while (l <= r) {
		ll mid = (l+r)/2;
		bool check = 1; reset(n+4);
		for (auto x : e) {
			if (x.len >= mid) break;
			unite(x.a, x.b);
		}
		check &= (find(1) != find(4));
		check &= (find(2) != find(4));
		check &= (find(3) != find(4));
		if (check == 0) r = mid-1;
		else l = mid+1, cur = mid;
	}
	dp[1][4] = dp[4][1] = cur;
	l = 0, r = min(w, h), cur = -1;
	while (l <= r) {
		ll mid = (l+r)/2;
		bool check = 1; reset(n+4);
		for (auto x : e) {
			if (x.len >= mid) break;
			unite(x.a, x.b);
		}
		check &= (find(1) != find(2));
		check &= (find(2) != find(3));
		check &= (find(2) != find(4));
		if (check == 0) r = mid-1;
		else l = mid+1, cur = mid; 
	}
	dp[2][3] = dp[3][2] = cur;
	l = 0, r = min(w, h), cur = -1;
	while (l <= r) {
		ll mid = (l+r)/2;
		bool check = 1; reset(n+4);
		for (auto x : e) {
			if (x.len >= mid) break;
			unite(x.a, x.b);
		}
		check &= (find(1) != find(2));
		check &= (find(1) != find(3));
		check &= (find(2) != find(4));
		check &= (find(3) != find(4));
		if (check == 0) r = mid-1;
		else l = mid+1, cur = mid; 
	}
	dp[2][4] = dp[4][2] = cur;
	l = 0, r = min(w, h), cur = -1;
	while (l <= r) {
		ll mid = (l+r)/2;
		bool check = 1; reset(n+4);
		for (auto x : e) {
			if (x.len >= mid) break;
			unite(x.a, x.b);
		}
		check &= (find(1) != find(3));
		check &= (find(2) != find(3));
		check &= (find(3) != find(4));
		if (check == 0) r = mid-1;
		else l = mid+1, cur = mid;
	}
	dp[3][4] = dp[4][3] = cur;
	while (m--) {
		int r, s; cin >> r >> s;
		for (int x = 1; x <= 4; x++) {
			if (dp[x][s] >= 2*r) cout << x;
		}
		cout << "\n";
	}
	cout << "\n"; return;
}
int main() {
    Ayano Kimishima
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1; while (t--) solve(); return 0;
}

Compilation message

park.cpp: In function 'void unite(int, int)':
park.cpp:29:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   29 |  if (u != v) dsu[v] = u; return;
      |  ^~
park.cpp:29:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   29 |  if (u != v) dsu[v] = u; return;
      |                          ^~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 33480 KB Output is correct
2 Correct 267 ms 33468 KB Output is correct
3 Correct 272 ms 33468 KB Output is correct
4 Correct 285 ms 33408 KB Output is correct
5 Correct 273 ms 33472 KB Output is correct
6 Correct 270 ms 33276 KB Output is correct
7 Correct 450 ms 33356 KB Output is correct
8 Correct 453 ms 33468 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 464 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2264 KB Output is correct
2 Correct 22 ms 2268 KB Output is correct
3 Correct 22 ms 2004 KB Output is correct
4 Correct 22 ms 2264 KB Output is correct
5 Correct 23 ms 2256 KB Output is correct
6 Correct 25 ms 2268 KB Output is correct
7 Correct 18 ms 1912 KB Output is correct
8 Correct 18 ms 1884 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 33480 KB Output is correct
2 Correct 267 ms 33468 KB Output is correct
3 Correct 272 ms 33468 KB Output is correct
4 Correct 285 ms 33408 KB Output is correct
5 Correct 273 ms 33472 KB Output is correct
6 Correct 270 ms 33276 KB Output is correct
7 Correct 450 ms 33356 KB Output is correct
8 Correct 453 ms 33468 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 464 KB Output is correct
11 Correct 23 ms 2264 KB Output is correct
12 Correct 22 ms 2268 KB Output is correct
13 Correct 22 ms 2004 KB Output is correct
14 Correct 22 ms 2264 KB Output is correct
15 Correct 23 ms 2256 KB Output is correct
16 Correct 25 ms 2268 KB Output is correct
17 Correct 18 ms 1912 KB Output is correct
18 Correct 18 ms 1884 KB Output is correct
19 Correct 294 ms 33732 KB Output is correct
20 Correct 280 ms 33560 KB Output is correct
21 Correct 297 ms 33732 KB Output is correct
22 Correct 284 ms 33728 KB Output is correct
23 Correct 288 ms 33732 KB Output is correct
24 Correct 456 ms 33736 KB Output is correct