oj.uz

Submission #544442

# Submission time Handle Problem Language Result Execution time Memory
544442 2022-04-01T23:41:22 Z rainboy Countries (BOI06_countries) C
100 / 100
 6 ms 340 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 280 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 3 ms 212 KB Output is correct
8 Correct 4 ms 212 KB Output is correct
9 Correct 5 ms 212 KB Output is correct
10 Correct 6 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 2 ms 212 KB Output is correct
16 Correct 2 ms 292 KB Output is correct
17 Correct 3 ms 212 KB Output is correct
18 Correct 4 ms 212 KB Output is correct
19 Correct 6 ms 312 KB Output is correct
20 Correct 5 ms 212 KB Output is correct