Submission #137502

# Submission time Handle Problem Language Result Execution time Memory
137502 2019-07-28T05:19:26 Z 김세빈(#3278) Countries (BOI06_countries) C++14
100 / 100
5 ms 408 KB
#include <bits/stdc++.h>

using namespace std;

int X[1010], Y[1010], S[1010], P[1010];
int n;

int find(int p) { return P[p] == p || !P[p]? p : P[p] = find(P[p]); }

int main()
{
	int i, j, d, mv, md, mc, mi;
	
	scanf("%d", &n);
	
	for(i=1; i<=n; i++){
		scanf("%d%d%d", X + i, Y + i, S + i);
	}
	
	for(i=1; i<=n; i++){
		mv = 0; md = 1;
		for(j=1; j<=n; j++){
			if(j == i) continue;
			d = (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]);
			if(S[j] * md > mv * d) mv = S[j], md = d, mc = 0, mi = j;
			if(S[j] * md == mv * d) mc ++;
		}
		
		if(mv > S[i] * md){
			if(mc == 1) P[i] = mi;
			else P[i] = 0;
		}
		else P[i] = i;
	}
	
	for(i=1; i<=n; i++){
		if(P[i] == 0) printf("D\n");
		else if(P[i] == i) printf("K\n");
		else printf("%d\n", find(i));
	}
	
	return 0;
}

Compilation message

countries.cpp: In function 'int main()':
countries.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
countries.cpp:17: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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
countries.cpp:30:21: warning: 'mi' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(mc == 1) P[i] = mi;
                ~~~~~^~~~
countries.cpp:26:31: warning: 'mc' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(S[j] * md == mv * d) mc ++;
                            ~~~^~
# 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 3 ms 408 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 376 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 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 2 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 376 KB Output is correct
18 Correct 4 ms 376 KB Output is correct
19 Correct 4 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct