Submission #544726

#	Time	Username	Problem	Language	Result	Execution time	Memory
544726		rainboy	Park (BOI16_park)	C++98	100 / 100	772 ms	33132 KiB

park

#include <math.h>
#include <stdio.h>
#include <string.h>

#define N	2000
#define M	(N * (N - 1) / 2 + N * 4)
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int ii[M], jj[M], rr_[M];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (rr_[hh[j]] == rr_[h])
				j++;
			else if (rr_[hh[j]] < rr_[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int ds[N + 4];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

int main() {
	static int xx[N], yy[N], rr[N], hh[M];
	int n, m, q, x_, y_, h, i, j, r12, r13, r14, r23, r24, r34;

	scanf("%d%d%d%d", &n, &q, &x_, &y_);
	for (i = 0; i < n; i++)
		scanf("%d%d%d", &xx[i], &yy[i], &rr[i]);
	m = 0;
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			ii[m] = i, jj[m] = j, rr_[m] = ((int) hypot(xx[i] - xx[j], yy[i] - yy[j]) - rr[i] - rr[j]) / 2 + 1, m++;

	for (i = 0; i < n; i++) {
		ii[m] = i, jj[m] = n, rr_[m] = (xx[i] - rr[i]) / 2 + 1, m++;
		ii[m] = i, jj[m] = n + 1, rr_[m] = (x_ - xx[i] - rr[i]) / 2 + 1, m++;
		ii[m] = i, jj[m] = n + 2, rr_[m] = (yy[i] - rr[i]) / 2 + 1, m++;
		ii[m] = i, jj[m] = n + 3, rr_[m] = (y_ - yy[i] - rr[i]) / 2 + 1, m++;
	}
	for (h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	memset(ds, -1, (n + 4) * sizeof *ds);
	r12 = r13 = r14 = r23 = r24 = r34 = INF;
	for (h = 0; h < m; h++) {
		int h_ = hh[h];

		join(ii[h_], jj[h_]);
		if (find(n + 2) == find(n) || find(n + 2) == find(n + 1) || find(n + 2) == find(n + 3))
			r12 = min(r12, rr_[h_]);
		if (find(n) == find(n + 1) || find(n + 2) == find(n + 3) || find(n) == find(n + 2) || find(n + 1) == find(n + 3))
			r13 = min(r13, rr_[h_]);
		if (find(n) == find(n + 1) || find(n) == find(n + 2) || find(n) == find(n + 3))
			r14 = min(r14, rr_[h_]);
		if (find(n + 1) == find(n) || find(n + 1) == find(n + 2) || find(n + 1) == find(n + 3))
			r23 = min(r23, rr_[h_]);
		if (find(n) == find(n + 1) || find(n + 2) == find(n + 3) || find(n + 1) == find(n + 2) || find(n) == find(n + 3))
			r24 = min(r24, rr_[h_]);
		if (find(n + 3) == find(n) || find(n + 3) == find(n + 1) || find(n + 3) == find(n + 2))
			r34 = min(r34, rr_[h_]);
	}
	while (q--) {
		int r, t;

		scanf("%d%d", &r, &t);
		if (t == 1) {
			printf("1");
			if (r < r12)
				printf("2");
			if (r < r13)
				printf("3");
			if (r < r14)
				printf("4");
		} else if (t == 2) {
			if (r < r12)
				printf("1");
			printf("2");
			if (r < r23)
				printf("3");
			if (r < r24)
				printf("4");
		} else if (t == 3) {
			if (r < r13)
				printf("1");
			if (r < r23)
				printf("2");
			printf("3");
			if (r < r34)
				printf("4");
		} else {
			if (r < r14)
				printf("1");
			if (r < r24)
				printf("2");
			if (r < r34)
				printf("3");
			printf("4");
		}
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d%d%d%d", &n, &q, &x_, &y_);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d%d%d", &xx[i], &yy[i], &rr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   scanf("%d%d", &r, &t);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42