Submission #137547

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

countries

#include<bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, x[N], y[N], s[N], c[N], d[N];

int sq (int X) {return X*X;}

int dist (int A, int B) {
	return sq(x[A]-x[B]) + sq(y[A]-y[B]);
}

int cmp (int X, int A, int B) {
	int V1 = s[A] * dist(X, B), V2 = s[B] * dist(X, A);
	return (V1 == V2 ? 0 : V1 > V2 ? -1 : 1);
}

bool win (int A, int B) {
	return s[A] > s[B] * dist(A, B);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d%d%d",&x[i],&y[i],&s[i]);
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			if(i == j || !win(j, i)) continue;
			if(!d[i]) {
				d[i] = j;
				c[i] = 1;
			}
			else {
				int T = cmp(i, d[i], j);
				if(T > 0) {
					d[i] = j;
					c[i] = 1;
				}
				else if(!T) c[i]++;
			}
		}
		if(c[i] > 1) d[i] = 0;
	}
	for(int i=1;i<=n;i++) {
		if(!d[i]) {
			puts(c[i] ? "D" : "K");
			continue;
		}
		int T = i;
		while(d[T]) T = d[T];
		printf("%d\n", T);
	}
}

Compilation message (stderr)

countries.cpp: In function 'int main()':
countries.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
countries.cpp:27: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