oj.uz

Submission #164725

# Submission time Handle Problem Language Result Execution time Memory
164725 2019-11-22T18:53:25 Z dolphingarlic Countries (BOI06_countries) C++14
100 / 100
 17 ms 508 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Country {
    int x, y, s, id;
};
bool operator<(Country A, Country B) {
    if (A.s == B.s) return A.id < B.id;
    return A.s > B.s;
};

int cmp[1000];
int find(int A) {
    while (A != cmp[A]) cmp[A] = cmp[cmp[A]], A = cmp[A];
    return A;
}
void onion(int A, int B) {
    cmp[find(A)] = cmp[find(B)];
}

Country c[1000];
string ans[1000];

double dist(Country A, Country B) {
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    FOR(i, 0, n) {
        cin >> c[i].x >> c[i].y >> c[i].s;
        c[i].id = i;
        cmp[i] = i;
    }
    sort(c, c + n);

    FOR(i, 0, n) {
        vector<pair<double, int>> v;
        FOR(j, 0, i) {
            double inf = c[j].s / dist(c[i], c[j]);
            if (inf > c[i].s) v.push_back({-inf, c[j].id});
        }
        sort(v.begin(), v.end());

        if (v.size()) {
            if (v.size() > 1 && v[0].first == v[1].first) ans[c[i].id] = "D";
            else {
                ans[c[i].id] = to_string(find(v[0].second) + 1);
                onion(c[i].id, v[0].second);
            }
        } else ans[c[i].id] = "K";
    }

    FOR(i, 0, n) cout << ans[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 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 5 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 4 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 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 3 ms 376 KB Output is correct
18 Correct 10 ms 376 KB Output is correct
19 Correct 17 ms 492 KB Output is correct
20 Correct 4 ms 508 KB Output is correct