Submission #1096518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096518		flo	Park (BOI16_park)	C++14	100 / 100	456 ms	33736 KiB

park

#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 (stderr)

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