Submission #917332

#	Time	Username	Problem	Language	Result	Execution time	Memory
917332		NK_	Park (BOI16_park)	C++17	100 / 100	671 ms	68076 KiB

park

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;

struct DSU {
	vi e; void init(int n) { e = vi(n, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool sameSet(int x, int y) { return get(x) == get(y); }
	bool unite(int x, int y) {
		// cout << x << " " << y << endl;
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};

const long double EPS = 1e-11;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	auto sq = [&](ll x) { return x * x; };

	int N, M; cin >> N >> M;

	int W, H; cin >> W >> H;

	V<array<int, 3>> A(N); for(auto& x : A) {
		cin >> x[0] >> x[1] >> x[2];
	}

	V<array<ll, 3>> Q(M); for(int i = 0; i < M; i++) {
		cin >> Q[i][0] >> Q[i][1]; Q[i][2] = i;
		Q[i][0] = sq(2 * Q[i][0]);
	}

	sort(begin(Q), end(Q));

	V<array<int, 2>> E; V<long double> EW;

	auto comp = [&](ll d, int ra, int rb) { 
		long double rt = sqrtl(d);
		long double dst = rt - ra - rb;
		// cout << dst * dst << endl;
		return dst * dst;
	};

	for(int i = 0; i < N; i++) {
		auto [xi, yi, ri] = A[i];

		EW.pb(comp(sq(xi), ri, 0)); E.pb({N, i}); // left wall
		EW.pb(comp(sq(yi), ri, 0)); E.pb({N + 1, i}); // bottom wall
		EW.pb(comp(sq(W - xi), ri, 0)); E.pb({N + 2, i}); // right wall
		EW.pb(comp(sq(H - yi), ri, 0)); E.pb({N + 3, i}); // top wall

		for(int j = i + 1; j < N; j++) {
			auto [xj, yj, rj] = A[j];

			ll odst = sq(xi - xj) + sq(yi - yj);
			EW.pb(comp(odst, ri, rj)); E.pb({i, j});
		}
	}

	vi ord(sz(E)); iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int x, int y) { return EW[x] + EPS < EW[y];  });
	// for(auto& i : ord) {
	// 	cout << EW[i] << " => " << E[i][0] << " " << E[i][1] << endl;
	// }

	int e = 0; DSU D; D.init(N + 4);
	V<string> ANS(M);
	for(auto& q : Q) {
		auto [r, s, i] = q; --s;

		while(e < sz(E) && (EW[ord[e]] + EPS) < r) {
			D.unite(E[ord[e]][0], E[ord[e]][1]); e++;
		}

		int op = (s + 2) % 4;
		bool opW = !D.sameSet(N + s, N + (s + 1) % 4);
		opW &= !D.sameSet(N + op, N + (op + 1) % 4);
		opW &= !D.sameSet(N + s, N + op);
		opW &= !D.sameSet(N + (s + 1) % 4, N + (op + 1) % 4);

		int nxt = (s + 1) % 4;
		bool nxtW = !D.sameSet(N + s, N + (s + 1) % 4);
		nxtW &= !D.sameSet(N + nxt, N + (nxt + 1) % 4);
		nxtW &= !D.sameSet(N + nxt, N + (nxt + 2) % 4);

		int prv = (s + 3) % 4;
		bool prvW = !D.sameSet(N + s, N + (s + 1) % 4);
		prvW &= !D.sameSet(N + prv, N + (prv + 1) % 4);
		prvW &= !D.sameSet(N + s, N + (s + 2) % 4);


		string ans = to_string(s + 1);
		if (opW) ans += to_string(op + 1);
		if (nxtW) ans += to_string(nxt + 1);
		if (prvW) ans += to_string(prv + 1);

		sort(begin(ans), end(ans));

		ANS[i] = ans;
	}

	for(auto& x : ANS) cout << x << nl;


	exit(0-0);
}

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