oj.uz

Submission #1066871

# Submission time Handle Problem Language Result Execution time Memory
1066871 2024-08-20T08:21:18 Z vjudge1 Park (BOI16_park) C++17
100 / 100
 450 ms 68004 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 439 ms 66096 KB Output is correct
2 Correct 426 ms 66508 KB Output is correct
3 Correct 440 ms 66240 KB Output is correct
4 Correct 423 ms 66760 KB Output is correct
5 Correct 424 ms 66208 KB Output is correct
6 Correct 411 ms 66364 KB Output is correct
7 Correct 398 ms 66160 KB Output is correct
8 Correct 438 ms 66168 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 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 28 ms 1492 KB Output is correct
5 Correct 16 ms 1492 KB Output is correct
6 Correct 16 ms 1492 KB Output is correct
7 Correct 13 ms 500 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 439 ms 66096 KB Output is correct
2 Correct 426 ms 66508 KB Output is correct
3 Correct 440 ms 66240 KB Output is correct
4 Correct 423 ms 66760 KB Output is correct
5 Correct 424 ms 66208 KB Output is correct
6 Correct 411 ms 66364 KB Output is correct
7 Correct 398 ms 66160 KB Output is correct
8 Correct 438 ms 66168 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 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 28 ms 1492 KB Output is correct
15 Correct 16 ms 1492 KB Output is correct
16 Correct 16 ms 1492 KB Output is correct
17 Correct 13 ms 500 KB Output is correct
18 Correct 13 ms 604 KB Output is correct
19 Correct 435 ms 66132 KB Output is correct
20 Correct 435 ms 67880 KB Output is correct
21 Correct 426 ms 66740 KB Output is correct
22 Correct 450 ms 66156 KB Output is correct
23 Correct 441 ms 66288 KB Output is correct
24 Correct 389 ms 68004 KB Output is correct