oj.uz

Submission #1066886

# Submission time Handle Problem Language Result Execution time Memory
1066886 2024-08-20T08:28:33 Z sleepntsheep Park (BOI16_park) C++17
100 / 100
 209 ms 25188 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 = 2e9;

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; }

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

void check_cut(int w) {
	if (cut1 == oo and ds_same(left(), down())) cut1 = w;
	if (cut2 == oo and ds_same(down(), right())) cut2 = w;
	if (cut3 == oo and ds_same(right(), up())) cut3 = w;
	if (cut4 == oo and ds_same(up(), left())) cut4 = w;
	if (cuth == oo and ds_same(left(), right())) cuth = w;
	if (cutv == oo 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<int, int, int>> el;

	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j)
			el.emplace_back((int)(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 188 ms 25028 KB Output is correct
2 Correct 185 ms 25024 KB Output is correct
3 Correct 189 ms 25028 KB Output is correct
4 Correct 188 ms 25028 KB Output is correct
5 Correct 194 ms 25028 KB Output is correct
6 Correct 205 ms 25028 KB Output is correct
7 Correct 165 ms 25028 KB Output is correct
8 Correct 166 ms 25024 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 15 ms 1112 KB Output is correct
2 Correct 15 ms 1112 KB Output is correct
3 Correct 14 ms 1112 KB Output is correct
4 Correct 14 ms 1092 KB Output is correct
5 Correct 14 ms 1112 KB Output is correct
6 Correct 14 ms 1028 KB Output is correct
7 Correct 14 ms 604 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 188 ms 25028 KB Output is correct
2 Correct 185 ms 25024 KB Output is correct
3 Correct 189 ms 25028 KB Output is correct
4 Correct 188 ms 25028 KB Output is correct
5 Correct 194 ms 25028 KB Output is correct
6 Correct 205 ms 25028 KB Output is correct
7 Correct 165 ms 25028 KB Output is correct
8 Correct 166 ms 25024 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 15 ms 1112 KB Output is correct
12 Correct 15 ms 1112 KB Output is correct
13 Correct 14 ms 1112 KB Output is correct
14 Correct 14 ms 1092 KB Output is correct
15 Correct 14 ms 1112 KB Output is correct
16 Correct 14 ms 1028 KB Output is correct
17 Correct 14 ms 604 KB Output is correct
18 Correct 13 ms 604 KB Output is correct
19 Correct 196 ms 25188 KB Output is correct
20 Correct 203 ms 25028 KB Output is correct
21 Correct 204 ms 25108 KB Output is correct
22 Correct 202 ms 25028 KB Output is correct
23 Correct 209 ms 25028 KB Output is correct
24 Correct 189 ms 25028 KB Output is correct