oj.uz

Submission #917332

# Submission time Handle Problem Language Result Execution time Memory
917332 2024-01-27T21:08:40 Z NK_ Park (BOI16_park) C++17
100 / 100
 671 ms 68076 KB 
// 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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 64028 KB Output is correct
2 Correct 603 ms 64040 KB Output is correct
3 Correct 603 ms 65056 KB Output is correct
4 Correct 621 ms 64640 KB Output is correct
5 Correct 601 ms 64040 KB Output is correct
6 Correct 599 ms 65352 KB Output is correct
7 Correct 454 ms 65288 KB Output is correct
8 Correct 392 ms 64292 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 6996 KB Output is correct
2 Correct 37 ms 6908 KB Output is correct
3 Correct 37 ms 6988 KB Output is correct
4 Correct 37 ms 7000 KB Output is correct
5 Correct 36 ms 6988 KB Output is correct
6 Correct 38 ms 7252 KB Output is correct
7 Correct 34 ms 6144 KB Output is correct
8 Correct 34 ms 6204 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 64028 KB Output is correct
2 Correct 603 ms 64040 KB Output is correct
3 Correct 603 ms 65056 KB Output is correct
4 Correct 621 ms 64640 KB Output is correct
5 Correct 601 ms 64040 KB Output is correct
6 Correct 599 ms 65352 KB Output is correct
7 Correct 454 ms 65288 KB Output is correct
8 Correct 392 ms 64292 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 36 ms 6996 KB Output is correct
12 Correct 37 ms 6908 KB Output is correct
13 Correct 37 ms 6988 KB Output is correct
14 Correct 37 ms 7000 KB Output is correct
15 Correct 36 ms 6988 KB Output is correct
16 Correct 38 ms 7252 KB Output is correct
17 Correct 34 ms 6144 KB Output is correct
18 Correct 34 ms 6204 KB Output is correct
19 Correct 667 ms 66856 KB Output is correct
20 Correct 663 ms 66892 KB Output is correct
21 Correct 641 ms 67108 KB Output is correct
22 Correct 671 ms 66812 KB Output is correct
23 Correct 656 ms 68076 KB Output is correct
24 Correct 485 ms 67172 KB Output is correct