oj.uz

Submission #917326

# Submission time Handle Problem Language Result Execution time Memory
917326 2024-01-27T20:48:12 Z NK_ Park (BOI16_park) C++17
0 / 100
 479 ms 51880 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;
	}
};

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; 	

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

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

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

# Verdict Execution time Memory Grader output
1 Correct 439 ms 50088 KB Output is correct
2 Correct 437 ms 49824 KB Output is correct
3 Correct 479 ms 50120 KB Output is correct
4 Correct 438 ms 50084 KB Output is correct
5 Correct 441 ms 50360 KB Output is correct
6 Correct 436 ms 51880 KB Output is correct
7 Correct 436 ms 51272 KB Output is correct
8 Incorrect 422 ms 51408 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 6860 KB Output is correct
2 Correct 145 ms 6860 KB Output is correct
3 Correct 144 ms 6876 KB Output is correct
4 Correct 139 ms 6772 KB Output is correct
5 Correct 137 ms 6856 KB Output is correct
6 Incorrect 141 ms 7068 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 50088 KB Output is correct
2 Correct 437 ms 49824 KB Output is correct
3 Correct 479 ms 50120 KB Output is correct
4 Correct 438 ms 50084 KB Output is correct
5 Correct 441 ms 50360 KB Output is correct
6 Correct 436 ms 51880 KB Output is correct
7 Correct 436 ms 51272 KB Output is correct
8 Incorrect 422 ms 51408 KB Output isn't correct
9 Halted 0 ms 0 KB -