Submission #137906

#	Time	Username	Problem	Language	Result	Execution time	Memory
137906		onjo0127	Countries (BOI06_countries)	C++11	100 / 100	5 ms	380 KiB

countries

#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 (stderr)

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 / 100