oj.uz

Submission #1066885

# Submission time Handle Problem Language Result Execution time Memory
1066885 2024-08-20T08:27:43 Z sleepntsheep Park (BOI16_park) C++17
100 / 100
 441 ms 66224 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); }

#define up() 2000
#define down() 2001
#define left() 2002
#define right() 2003


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 < 2004; ++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:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d%d%d", &n, &m, &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:44:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  for (int i = 0; i < n; ++i) scanf("%d%d%d", x + i, y + i, r + i);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d%d", &rad, &corner);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 66208 KB Output is correct
2 Correct 419 ms 66212 KB Output is correct
3 Correct 441 ms 66212 KB Output is correct
4 Correct 422 ms 66208 KB Output is correct
5 Correct 411 ms 66212 KB Output is correct
6 Correct 410 ms 66204 KB Output is correct
7 Correct 381 ms 66212 KB Output is correct
8 Correct 379 ms 66140 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 16 ms 1492 KB Output is correct
5 Correct 15 ms 1488 KB Output is correct
6 Correct 16 ms 1492 KB Output is correct
7 Correct 14 ms 604 KB Output is correct
8 Correct 12 ms 592 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 66208 KB Output is correct
2 Correct 419 ms 66212 KB Output is correct
3 Correct 441 ms 66212 KB Output is correct
4 Correct 422 ms 66208 KB Output is correct
5 Correct 411 ms 66212 KB Output is correct
6 Correct 410 ms 66204 KB Output is correct
7 Correct 381 ms 66212 KB Output is correct
8 Correct 379 ms 66140 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 16 ms 1492 KB Output is correct
15 Correct 15 ms 1488 KB Output is correct
16 Correct 16 ms 1492 KB Output is correct
17 Correct 14 ms 604 KB Output is correct
18 Correct 12 ms 592 KB Output is correct
19 Correct 430 ms 66012 KB Output is correct
20 Correct 422 ms 66224 KB Output is correct
21 Correct 426 ms 66212 KB Output is correct
22 Correct 420 ms 66212 KB Output is correct
23 Correct 423 ms 66080 KB Output is correct
24 Correct 397 ms 66104 KB Output is correct