Submission #137497

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137497	2019-07-28T05:04:47 Z	윤교준(#3280)	Countries (BOI06_countries)	C++14	100 / 100	8 ms	412 KB

countries

#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

#	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	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