oj.uz

Submission #137906

# Submission time Handle Problem Language Result Execution time Memory
137906 2019-07-28T13:45:49 Z onjo0127 Countries (BOI06_countries) C++11
100 / 100
 5 ms 380 KB 
#include <bits/stdc++.h>
using namespace std;

int N, x[1009], y[1009], s[1009], p[1009];
char ans[1009];

int root(int x) {
	if(p[x] == x) return x;
	return p[x] = root(p[x]);
}

void merg(int u, int v) {
	u = root(u); v = root(v);
	p[u] = v;
}

int dst(int i, int j) {
	return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
}

int main() {
	scanf("%d",&N);
	for(int i=1; i<=N; i++) {
		scanf("%d%d%d", &x[i], &y[i], &s[i]);
		p[i] = i;
	}
	for(int i=1; i<=N; i++) {
		int mxi = -1, c = 0;
		for(int j=1; j<=N; j++) {
			if(i == j) continue;
			if(s[j] > s[i] * dst(i, j)) {
				if(mxi == -1) mxi = j, c = 1;
				else if(s[j] * dst(i, mxi) > s[mxi] * dst(i, j)) mxi = j, c = 1;
				else if(s[j] * dst(i, mxi) == s[mxi] * dst(i, j)) ++c;
			}
		}
		if(mxi == -1) ans[i] = 'K';
		else if(c > 1) ans[i] = 'D';
		else {
			ans[i] = 'O';
			merg(i, mxi);
		}
	}
	for(int i=1; i<=N; i++) {
		if(ans[i] == 'O') printf("%d\n", root(i));
		else printf("%c\n", ans[i]);
	}
	return 0;
}

Compilation message

countries.cpp: In function 'int main()':
countries.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
countries.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x[i], &y[i], &s[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 380 KB Output is correct
8 Correct 4 ms 360 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 380 KB Output is correct
16 Correct 3 ms 380 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 4 ms 296 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 4 ms 376 KB Output is correct