oj.uz

Submission #938643

# Submission time Handle Problem Language Result Execution time Memory
938643 2024-03-05T11:38:17 Z mnbvcxz123 Park (BOI16_park) C++17
100 / 100
 628 ms 54720 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::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 572 ms 51428 KB Output is correct
2 Correct 602 ms 52224 KB Output is correct
3 Correct 603 ms 52216 KB Output is correct
4 Correct 582 ms 52336 KB Output is correct
5 Correct 587 ms 52216 KB Output is correct
6 Correct 571 ms 51188 KB Output is correct
7 Correct 512 ms 51884 KB Output is correct
8 Correct 515 ms 51884 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 4236 KB Output is correct
2 Correct 36 ms 3984 KB Output is correct
3 Correct 34 ms 3888 KB Output is correct
4 Correct 34 ms 3980 KB Output is correct
5 Correct 34 ms 4160 KB Output is correct
6 Correct 36 ms 4000 KB Output is correct
7 Correct 32 ms 3536 KB Output is correct
8 Correct 36 ms 3612 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 51428 KB Output is correct
2 Correct 602 ms 52224 KB Output is correct
3 Correct 603 ms 52216 KB Output is correct
4 Correct 582 ms 52336 KB Output is correct
5 Correct 587 ms 52216 KB Output is correct
6 Correct 571 ms 51188 KB Output is correct
7 Correct 512 ms 51884 KB Output is correct
8 Correct 515 ms 51884 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 4236 KB Output is correct
12 Correct 36 ms 3984 KB Output is correct
13 Correct 34 ms 3888 KB Output is correct
14 Correct 34 ms 3980 KB Output is correct
15 Correct 34 ms 4160 KB Output is correct
16 Correct 36 ms 4000 KB Output is correct
17 Correct 32 ms 3536 KB Output is correct
18 Correct 36 ms 3612 KB Output is correct
19 Correct 628 ms 54720 KB Output is correct
20 Correct 612 ms 53008 KB Output is correct
21 Correct 602 ms 53568 KB Output is correct
22 Correct 593 ms 53304 KB Output is correct
23 Correct 606 ms 54492 KB Output is correct
24 Correct 545 ms 52904 KB Output is correct