Submission #231034

#	Time	Username	Problem	Language	Result	Execution time	Memory
231034		islingr	Park (BOI16_park)	C++14	0 / 100	511 ms	37596 KiB

park

#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
using point = complex<int>;
using pii = pair<int, int>;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define eb(x...) emplace_back(x)

#define f first
#define s second

ll abs(point p) {
	ll z = 1ll * real(p) * real(p) + 1ll * imag(p) * imag(p);
	ld h = hypot(ld(real(p)), ld(imag(p)));
	ll x = round(h);
	if (x * x == z) return x;
	else return ceil(h);
}
struct event {
	int r, c, i;
	bool operator<(const event &e) { return r < e.r; } 
};

constexpr int N = 1 << 11, M = 1 << 17;
int nxt[N], rnk[N], r[N], n, m, w, h;
point p[N];
event v[M];
string ans[M];
vector<pair<ll, pii>> q;
vector<pii> c[4][4] = {
		{{}, {{1, 3}, {1, 0}, {1, 2}}, {{1, 0}, {1, 3}, {2, 0}, {2, 3}}, {{0, 1}, {0, 2}, {0, 3}}},
		{{{1, 3}, {1, 0}, {1, 2}}, {}, {{2, 1}, {2, 0}, {2, 3}}, {{1, 2}, {1, 3}, {0, 2}, {0, 3}}},
		{{{2, 3}, {0, 1}, {1, 3}, {0, 2}}, {{0, 2}, {1, 2}, {2, 3}}, {}, {{1, 3}, {2, 3}, {0, 3}}},
		{{{0, 3}, {0, 2}, {0, 1}}, {{3, 0}, {3, 1}, {2, 0}, {2, 1}}, {{1, 3}, {0, 3}, {2, 3}}, {}}
	};

int head(int u) { return nxt[u] != -1 ? nxt[u] = head(nxt[u]) : u; }
void unite(int u, int v) {
	u = head(u); v = head(v);
	if (u == v) return;
	if (rnk[u] < rnk[v]) nxt[u] = v;
	else {
		nxt[v] = u;
		if (rnk[u] == rnk[v]) ++rnk[u];
	}
}
bool same(int u, int v) { return head(u) == head(v); }
void unite(pii p) { unite(p.f, p.s); }

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m >> w >> h;
	rep(i, 0, n) {
		int x, y; cin >> x >> y >> r[i];
		p[i] = {x, y};
	}

	rep(i, 0, n) {
		int x = real(p[i]), y = imag(p[i]);
		q.eb(x - r[i], pii(i, n));
		q.eb(y - r[i], pii(i, n + 1));
		q.eb(w - x - r[i], pii(i, n + 2));
		q.eb(h - y - r[i], pii(i, n + 3));
	}
	rep(i, 0, n) rep(j, i + 1, n) q.eb(abs(p[i] - p[j]) - r[i] - r[j], pii(i, j));
	sort(rall(q));
	rep(u, 0, n + 4) nxt[u] = -1;
	rep(i, 0, m) {
		cin >> v[i].r >> v[i].c; --v[i].c;
		v[i].i = i;
	}
	sort(v, v + m);
	// trav(x, q) cout << x.f << " (" << x.s.f << ", " << x.s.s << ")\n";

	rep(i, 0, m) {
		while (!q.empty() && q.back().f <= 2 * v[i].r) {
			unite(q.back().s); q.pop_back();
		}
		rep(j, 0, 4) {
			bool works = true;
			trav(x, c[v[i].c][j])
				if (same(x.f + n, x.s + n))
					works = false;
			if (works) ans[v[i].i] += '1' + j;
		}
	}

	rep(i, 0, m) cout << ans[i] << '\n';
}

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42