oj.uz

Submission #952279

# Submission time Handle Problem Language Result Execution time Memory
952279 2024-03-23T13:36:26 Z Trisanu_Das Park (BOI16_park) C++17
100 / 100
 620 ms 54776 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair

const int MX = 2006;

vector<pair<ll, pair<pi, pi>>> ed;
map<pi, int> cc;

template <int SZ> struct DSU {
	int p[SZ], sz[SZ];
	void init() {
		for (int i = 0; i < SZ; i++) {
			p[i] = i;
			sz[i] = 1;
		}
	}
	int find(int x) { return p[x] = (p[x] == x ? x : find(p[x])); }
	void merge(int u, int v) {
		int a = find(u);
		int b = find(v);
		if (a != b) {
			if (sz[a] < sz[b]) { swap(a, b); }
			p[b] = a;
			sz[a] += sz[b];
		}
	}
};

DSU<MX> dsu;
bool ok[100005][4];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m, w, h;
	cin >> n >> m >> w >> h;
	vector<pair<pair<ll, ll>, int>> trees(n);
	set<pi> pts;
	auto dist = [&](int x1, int y1, int x2, int y2) {
		return sqrt((1LL * (x2 - x1) * (x2 - x1)) +
		            (1LL * (y2 - y1) * (y2 - y1)));
	};
	auto add = [&](int x1, int y1, int x2, int y2, ll r1, ll r2) {
		ll ndist = dist(x1, y1, x2, y2) - r1 - r2;
		ed.pb(mp(ndist, mp(mp(x1, y1), mp(x2, y2))));
	};
	for (int i = 0; i < n; i++) {
		cin >> trees[i].f.f >> trees[i].f.s >> trees[i].s;
		pts.insert(mp(trees[i].f.f, trees[i].f.s));
		cc[mp(0, trees[i].f.s)] = 3;
		cc[mp(trees[i].f.f, h)] = 2;
		cc[mp(w, trees[i].f.s)] = 1;
		cc[mp(trees[i].f.f, 0)] = 0;
		add(trees[i].f.f, trees[i].f.s, 0, trees[i].f.s, trees[i].s, 0);
		add(trees[i].f.f, trees[i].f.s, trees[i].f.f, 0, trees[i].s, 0);
		add(trees[i].f.f, trees[i].f.s, w, trees[i].f.s, trees[i].s, 0);
		add(trees[i].f.f, trees[i].f.s, trees[i].f.f, h, trees[i].s, 0);
	}
	int cnt = 4;
	for (pi x : pts) { cc[x] = cnt++; }
	assert(cnt <= n + 4);
	for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) add(trees[i].f.f, trees[i].f.s, trees[j].f.f, trees[j].f.s, trees[i].s, trees[j].s);
	vector<pair<pi, int>> qrs;
	for (int i = 0; i < m; i++) {
		int r, e;
		cin >> r >> e;
		e--;
		qrs.pb(mp(mp(2 * r, e), i));
	}
	sort(all(qrs));
	sort(all(ed));
	dsu.init();
	int p = 0;
	memset(ok, true, sizeof(ok));
	for (auto v : ed) {
		while (p < sz(qrs) && qrs[p].f.f <= v.f) {
			bool conn[4][4];
			pair<pi, int> curr = qrs[p];
			for (int i = 0; i < 4; i++) {
				conn[i][i] = true;
				for (int j = i + 1; j < 4; j++) {
					conn[i][j] = (dsu.find(i) == dsu.find(j));
					conn[j][i] = conn[i][j];
				}
			}
			auto bad = [&](const int &x) {
				return conn[(x - 1 < 0 ? 3 : x - 1)][x];
			};
			for (int i = 0; i < 4; i++) {
				if (curr.f.s == i) { continue; }
				if (bad(curr.f.s) || bad(i)) {
					ok[curr.s][i] = false;
					continue;
				}
				bool upok = conn[0][2];
				bool sok = conn[1][3];
				if (abs(curr.f.s - i) == 2) {
					if (upok || sok) {
						ok[curr.s][i] = false;
						continue;
					}
				} else if (curr.f.s + i == 3) {
					if (sok) {
						ok[curr.s][i] = false;
						continue;
					}
				} else if (upok) ok[curr.s][i] = false;
			}
			++p;
			if (p >= sz(qrs)) break;
		}
		dsu.merge(cc[v.s.f], cc[v.s.s]);
	}
	for (int i = 0; i < m; i++) {
		string ret = "";
		for (int j = 0; j < 4; j++) if (ok[i][j]) ret += to_string(j + 1);
		cout << ret << '\n';
	}
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 51452 KB Output is correct
2 Correct 579 ms 51432 KB Output is correct
3 Correct 565 ms 51688 KB Output is correct
4 Correct 567 ms 51396 KB Output is correct
5 Correct 578 ms 51036 KB Output is correct
6 Correct 568 ms 51444 KB Output is correct
7 Correct 508 ms 50680 KB Output is correct
8 Correct 515 ms 50432 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3980 KB Output is correct
2 Correct 34 ms 3984 KB Output is correct
3 Correct 34 ms 3980 KB Output is correct
4 Correct 35 ms 4156 KB Output is correct
5 Correct 34 ms 3992 KB Output is correct
6 Correct 35 ms 4084 KB Output is correct
7 Correct 33 ms 3524 KB Output is correct
8 Correct 31 ms 3536 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 51452 KB Output is correct
2 Correct 579 ms 51432 KB Output is correct
3 Correct 565 ms 51688 KB Output is correct
4 Correct 567 ms 51396 KB Output is correct
5 Correct 578 ms 51036 KB Output is correct
6 Correct 568 ms 51444 KB Output is correct
7 Correct 508 ms 50680 KB Output is correct
8 Correct 515 ms 50432 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 35 ms 3980 KB Output is correct
12 Correct 34 ms 3984 KB Output is correct
13 Correct 34 ms 3980 KB Output is correct
14 Correct 35 ms 4156 KB Output is correct
15 Correct 34 ms 3992 KB Output is correct
16 Correct 35 ms 4084 KB Output is correct
17 Correct 33 ms 3524 KB Output is correct
18 Correct 31 ms 3536 KB Output is correct
19 Correct 620 ms 53900 KB Output is correct
20 Correct 605 ms 53848 KB Output is correct
21 Correct 615 ms 53464 KB Output is correct
22 Correct 610 ms 54776 KB Output is correct
23 Correct 596 ms 53960 KB Output is correct
24 Correct 544 ms 52764 KB Output is correct