oj.uz

Submission #1066872

# Submission time Handle Problem Language Result Execution time Memory
1066872 2024-08-20T08:21:28 Z sleepntsheep Park (BOI16_park) C++17
100 / 100
 422 ms 68204 KB 
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <tuple>

using ll = long long;
using ld = long double;

using namespace std;
template <typename T>
using ve = vector<T>;

const ll oo = 1e18;

int n, m, w, h, x[2002], y[2002], r[2005], ds[2005];

int ds_find(int i) { return ds[i] < 0 ? i : (ds[i] = ds_find(ds[i])); }
int ds_same(int i, int j) { return ds_find(i) == ds_find(j); }

int up() { return n; }
int down() { return n + 1; }
int left() { return n + 2; }
int right() { return n + 3; }

ll sqre(int x) { return x * 1ll * x; }

ll cut1{oo}, cut2{oo}, cut3{oo}, cut4{oo}, cutv{oo}, cuth{oo};

void check_cut(ll w) {
	if (cut1 == 1e18 and ds_same(left(), down())) cut1 = w;
	if (cut2 == 1e18 and ds_same(down(), right())) cut2 = w;
	if (cut3 == 1e18 and ds_same(right(), up())) cut3 = w;
	if (cut4 == 1e18 and ds_same(up(), left())) cut4 = w;
	if (cuth == 1e18 and ds_same(left(), right())) cuth = w;
	if (cutv == 1e18 and ds_same(down(), up())) cutv = w;
}

int main() {
	scanf("%d%d%d%d", &n, &m, &w, &h);

	for (int i = 0; i < n + 4; ++i) ds[i] = -1;
	for (int i = 0; i < n; ++i) scanf("%d%d%d", x + i, y + i, r + i);

	ve<tuple<ld, int, int>> el;

	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j)
			el.emplace_back((long long)(sqrtl(sqre(x[i] - x[j]) + sqre(y[i] - y[j])) - r[i] - r[j]), i, j);
		el.emplace_back(x[i] - r[i], left(), i);
		el.emplace_back(w - x[i] - r[i], right(), i);
		el.emplace_back(y[i] - r[i], down(), i);
		el.emplace_back(h - y[i] - r[i], up(), i);
	}

	sort(el.begin(), el.end());

	for (auto [w, u, v] : el) {
		if (ds_same(u, v)) continue;
		ds[ds_find(u)] = v;
		check_cut(w);
	}

	while (m--) {
		int corner, rad;
		scanf("%d%d", &rad, &corner);
		rad *= 2;
		switch (corner) {
			case 1:
				putchar('1');
				if (cutv >= rad and cut1 >= rad and cut2 >= rad)
					putchar('2');
				if (cutv >= rad and cuth >= rad and cut1 >= rad and cut3 >= rad)
					putchar('3');
				if (cuth >= rad and cut1 >= rad and cut4 >= rad)
					putchar('4');
				break;
			case 2:
				if (cutv >= rad and cut1 >= rad and cut2 >= rad)
					putchar('1');
				putchar('2');
				if (cuth >= rad and cut2 >= rad and cut3 >= rad)
					putchar('3');
				if (cutv >= rad and cuth >= rad and cut4 >= rad and cut2 >= rad)
					putchar('4');
				break;
			case 3:
				if (cutv >= rad and cuth >= rad and cut1 >= rad and cut3 >= rad)
					putchar('1');
				if (cuth >= rad and cut2 >= rad and cut3 >= rad)
					putchar('2');
				putchar('3');
				if (cutv >= rad and cut3 >= rad and cut4 >= rad)
					putchar('4');
				break;
			case 4:
				if (cuth >= rad and cut1 >= rad and cut4 >= rad)
					putchar('1');
				if (cutv >= rad and cuth >= rad and cut4 >= rad and cut2 >= rad)
					putchar('2');
				if (cutv >= rad and cut3 >= rad and cut4 >= rad)
					putchar('3');
				putchar('4');
				break;
		}
		putchar('\n');
	}

	return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d%d%d%d", &n, &m, &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:43:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  for (int i = 0; i < n; ++i) scanf("%d%d%d", x + i, y + i, r + i);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d%d", &rad, &corner);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 67264 KB Output is correct
2 Correct 403 ms 66980 KB Output is correct
3 Correct 406 ms 66948 KB Output is correct
4 Correct 409 ms 66464 KB Output is correct
5 Correct 409 ms 67748 KB Output is correct
6 Correct 406 ms 66492 KB Output is correct
7 Correct 369 ms 66472 KB Output is correct
8 Correct 377 ms 66716 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1492 KB Output is correct
2 Correct 16 ms 1492 KB Output is correct
3 Correct 16 ms 1492 KB Output is correct
4 Correct 16 ms 1488 KB Output is correct
5 Correct 16 ms 1492 KB Output is correct
6 Correct 16 ms 1492 KB Output is correct
7 Correct 12 ms 664 KB Output is correct
8 Correct 13 ms 604 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 67264 KB Output is correct
2 Correct 403 ms 66980 KB Output is correct
3 Correct 406 ms 66948 KB Output is correct
4 Correct 409 ms 66464 KB Output is correct
5 Correct 409 ms 67748 KB Output is correct
6 Correct 406 ms 66492 KB Output is correct
7 Correct 369 ms 66472 KB Output is correct
8 Correct 377 ms 66716 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 16 ms 1492 KB Output is correct
12 Correct 16 ms 1492 KB Output is correct
13 Correct 16 ms 1492 KB Output is correct
14 Correct 16 ms 1488 KB Output is correct
15 Correct 16 ms 1492 KB Output is correct
16 Correct 16 ms 1492 KB Output is correct
17 Correct 12 ms 664 KB Output is correct
18 Correct 13 ms 604 KB Output is correct
19 Correct 415 ms 67760 KB Output is correct
20 Correct 418 ms 68204 KB Output is correct
21 Correct 416 ms 66212 KB Output is correct
22 Correct 419 ms 67004 KB Output is correct
23 Correct 422 ms 67744 KB Output is correct
24 Correct 384 ms 66212 KB Output is correct