oj.uz

Submission #137547

# Submission time Handle Problem Language Result Execution time Memory
137547 2019-07-28T06:24:46 Z khsoo01 Countries (BOI06_countries) C++11
100 / 100
 5 ms 380 KB 
#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

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.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 376 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 5 ms 380 KB Output is correct
11 Correct 2 ms 380 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 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 ms 252 KB Output is correct
18 Correct 4 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 4 ms 376 KB Output is correct