oj.uz

Submission #1066864

# Submission time Handle Problem Language Result Execution time Memory
1066864 2024-08-20T08:18:46 Z sleepntsheep Park (BOI16_park) C++17
100 / 100
 432 ms 68064 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#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] + 1e-7), 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);
	}

	//printf("%Lf %Lf %Lf %Lf %Lf %Lf\n",cut1,cut2,cut3,cut4,cutv,cuth);

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

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 67492 KB Output is correct
2 Correct 397 ms 67260 KB Output is correct
3 Correct 405 ms 68064 KB Output is correct
4 Correct 415 ms 66864 KB Output is correct
5 Correct 414 ms 66976 KB Output is correct
6 Correct 413 ms 66468 KB Output is correct
7 Correct 371 ms 66988 KB Output is correct
8 Correct 376 ms 67744 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1488 KB Output is correct
2 Correct 16 ms 1492 KB Output is correct
3 Correct 17 ms 1488 KB Output is correct
4 Correct 16 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 644 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 407 ms 67492 KB Output is correct
2 Correct 397 ms 67260 KB Output is correct
3 Correct 405 ms 68064 KB Output is correct
4 Correct 415 ms 66864 KB Output is correct
5 Correct 414 ms 66976 KB Output is correct
6 Correct 413 ms 66468 KB Output is correct
7 Correct 371 ms 66988 KB Output is correct
8 Correct 376 ms 67744 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 18 ms 1488 KB Output is correct
12 Correct 16 ms 1492 KB Output is correct
13 Correct 17 ms 1488 KB Output is correct
14 Correct 16 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 644 KB Output is correct
18 Correct 13 ms 604 KB Output is correct
19 Correct 423 ms 67516 KB Output is correct
20 Correct 417 ms 67760 KB Output is correct
21 Correct 430 ms 67424 KB Output is correct
22 Correct 432 ms 67936 KB Output is correct
23 Correct 432 ms 67488 KB Output is correct
24 Correct 388 ms 66360 KB Output is correct