oj.uz

Submission #626869

# Submission time Handle Problem Language Result Execution time Memory
626869 2022-08-11T22:10:28 Z tonfai_nokhong Park (BOI16_park) C++17
100 / 100
 776 ms 52764 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 688 ms 50400 KB Output is correct
2 Correct 716 ms 50300 KB Output is correct
3 Correct 703 ms 50392 KB Output is correct
4 Correct 721 ms 50376 KB Output is correct
5 Correct 741 ms 50404 KB Output is correct
6 Correct 683 ms 50392 KB Output is correct
7 Correct 618 ms 50116 KB Output is correct
8 Correct 637 ms 50140 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 724 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3916 KB Output is correct
2 Correct 43 ms 3908 KB Output is correct
3 Correct 44 ms 3880 KB Output is correct
4 Correct 47 ms 3956 KB Output is correct
5 Correct 45 ms 3932 KB Output is correct
6 Correct 42 ms 3976 KB Output is correct
7 Correct 48 ms 3432 KB Output is correct
8 Correct 42 ms 3380 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 50400 KB Output is correct
2 Correct 716 ms 50300 KB Output is correct
3 Correct 703 ms 50392 KB Output is correct
4 Correct 721 ms 50376 KB Output is correct
5 Correct 741 ms 50404 KB Output is correct
6 Correct 683 ms 50392 KB Output is correct
7 Correct 618 ms 50116 KB Output is correct
8 Correct 637 ms 50140 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 45 ms 3916 KB Output is correct
12 Correct 43 ms 3908 KB Output is correct
13 Correct 44 ms 3880 KB Output is correct
14 Correct 47 ms 3956 KB Output is correct
15 Correct 45 ms 3932 KB Output is correct
16 Correct 42 ms 3976 KB Output is correct
17 Correct 48 ms 3432 KB Output is correct
18 Correct 42 ms 3380 KB Output is correct
19 Correct 755 ms 52628 KB Output is correct
20 Correct 757 ms 52636 KB Output is correct
21 Correct 749 ms 52764 KB Output is correct
22 Correct 752 ms 52644 KB Output is correct
23 Correct 776 ms 52640 KB Output is correct
24 Correct 702 ms 52508 KB Output is correct