oj.uz

Submission #917331

# Submission time Handle Problem Language Result Execution time Memory
917331 2024-01-27T21:05:25 Z NK_ Park (BOI16_park) C++17
100 / 100
 842 ms 69356 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-9;

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 << endl;


	exit(0-0);
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 65064 KB Output is correct
2 Correct 645 ms 64292 KB Output is correct
3 Correct 626 ms 65316 KB Output is correct
4 Correct 608 ms 63780 KB Output is correct
5 Correct 618 ms 64056 KB Output is correct
6 Correct 644 ms 65796 KB Output is correct
7 Correct 452 ms 63780 KB Output is correct
8 Correct 397 ms 64696 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 600 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 6968 KB Output is correct
2 Correct 137 ms 6988 KB Output is correct
3 Correct 139 ms 6992 KB Output is correct
4 Correct 138 ms 6992 KB Output is correct
5 Correct 148 ms 7000 KB Output is correct
6 Correct 142 ms 6972 KB Output is correct
7 Correct 136 ms 7248 KB Output is correct
8 Correct 139 ms 7248 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 65064 KB Output is correct
2 Correct 645 ms 64292 KB Output is correct
3 Correct 626 ms 65316 KB Output is correct
4 Correct 608 ms 63780 KB Output is correct
5 Correct 618 ms 64056 KB Output is correct
6 Correct 644 ms 65796 KB Output is correct
7 Correct 452 ms 63780 KB Output is correct
8 Correct 397 ms 64696 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 140 ms 6968 KB Output is correct
12 Correct 137 ms 6988 KB Output is correct
13 Correct 139 ms 6992 KB Output is correct
14 Correct 138 ms 6992 KB Output is correct
15 Correct 148 ms 7000 KB Output is correct
16 Correct 142 ms 6972 KB Output is correct
17 Correct 136 ms 7248 KB Output is correct
18 Correct 139 ms 7248 KB Output is correct
19 Correct 743 ms 69356 KB Output is correct
20 Correct 792 ms 68592 KB Output is correct
21 Correct 842 ms 68900 KB Output is correct
22 Correct 747 ms 68988 KB Output is correct
23 Correct 745 ms 69272 KB Output is correct
24 Correct 610 ms 67696 KB Output is correct