Submission #544442

#	Time	Username	Problem	Language	Result	Execution time	Memory
544442		rainboy	Countries (BOI06_countries)	C11	100 / 100	6 ms	340 KiB

countries

#include <stdio.h>

#define N	1000

int pp[N];

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

int main() {
	static int xx[N], yy[N], ss[N];
	int n, i, j;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d%d", &xx[i], &yy[i], &ss[i]);
	for (i = 0; i < n; i++) {
		int j_, d2_;

		j_ = -1, d2_ = -1;
		for (j = 0; j < n; j++)
			if (j != i) {
				int x = xx[i] - xx[j], y = yy[i] - yy[j], d2 = x * x + y * y;

				if (j_ == -1 || ss[j_] * d2 < ss[j] * d2_)
					j_ = j, d2_ = d2;
			}
		if (j_ != -1 && ss[i] * d2_ < ss[j_]) {
			for (j = 0; j < n; j++)
				if (j != i && j != j_) {
					int x = xx[i] - xx[j], y = yy[i] - yy[j], d2 = x * x + y * y;

					if (ss[j_] * d2 == ss[j] * d2_) {
						j_ = -1;
						break;
					}
				}
			if (j_ == -1)
				pp[i] = -2;
			else
				pp[i] = j_;
		} else
			pp[i] = -1;
	}
	for (i = 0; i < n; i++)
		find(i);
	for (i = 0; i < n; i++)
		if (pp[i] == -1)
			printf("K\n");
		else if (pp[i] == -2)
			printf("D\n");
		else
			printf("%d\n", pp[i] + 1);
	return 0;
}

Compilation message (stderr)

countries.c: In function 'main':
countries.c:15:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
countries.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d%d%d", &xx[i], &yy[i], &ss[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100