Submission #917324

#	Time	Username	Problem	Language	Result	Execution time	Memory
917324		NK_	Park (BOI16_park)	C++17	0 / 100	262 ms	50040 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;
	}
};

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<ll, 3>> E; 	

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

		E.pb({sq(xi - 1) - sq(ri), N, i}); // left wall
		E.pb({sq(yi - 1) - sq(ri), N + 1, i}); // bottom wall
		E.pb({sq(W - xi) - sq(ri), N + 2, i}); // right wall
		E.pb({sq(H - yi) - sq(ri), 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);
			ll rdst = sq(ri) + sq(rj);

			ll dst = odst - rdst;
			E.pb({dst, i, j});
		}
	}

	sort(begin(E), end(E));
	// for(auto& e : E) cout << e[0] << " => " << e[1] << " " << e[2] << 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) && E[e][0] <= r) {
			D.unite(E[e][1], E[e][2]); 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 << endl;


	exit(0-0);
}

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