oj.uz

답안 #137497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137497 2019-07-28T05:04:47 Z 윤교준(#3280) Countries (BOI06_countries) C++14
100 / 100
 8 ms 412 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
using namespace std;
typedef long long ll;
ll pw(ll n) { return n*n; }

const int MAXN = 1005;

vector<int> V[MAXN];

int A[MAXN], B[MAXN], C[MAXN];
int O[MAXN], D[MAXN];

int N;

ll getDist(int a, int b) { return pw(A[a]-A[b]) + pw(B[a]-B[b]); }

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N;
	for(int i = 1; i <= N; i++)
		cin >> A[i] >> B[i] >> C[i];
	iota(O, O+N+1, 0); sort(O+1, O+N+1, [&](int a, int b) {
		return C[a] > C[b];
	});

	for(int oi = 1, i; oi <= N; oi++) {
		i = O[oi];
		for(int j = 1; j <= N; j++) if(j != i) {
			if(C[i] <= C[j] * getDist(i, j)) continue;
			if(V[j].empty()) {
				V[j].eb(i);
				continue;
			}
			int k = V[j][0];
			ll tk = C[k] * getDist(i, j);
			ll ti = C[i] * getDist(k, j);
			if(ti < tk) continue;
			if(tk < ti) V[j].clear();
			V[j].eb(i);
		}
	}

	for(int oi = 1, i; oi <= N; oi++) {
		i = O[oi];
		if(V[i].empty()) {
			D[i] = i;
			continue;
		}
		if(1 < sz(V[i])) {
			D[i] = -1;
			continue;
		}
		D[i] = D[V[i][0]];
	}

	for(int i = 1; i <= N; i++) {
		if(D[i] == i) cout << "K\n";
		else if(-1 == D[i]) cout << "D\n";
		else cout << D[i] << '\n';
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 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 376 KB Output is correct
5 Correct 3 ms 404 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 4 ms 412 KB Output is correct
9 Correct 5 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 3 ms 380 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 4 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 8 ms 376 KB Output is correct
20 Correct 6 ms 380 KB Output is correct