Submission #758248

# Submission time Handle Problem Language Result Execution time Memory
758248 2023-06-14T10:16:51 Z nguyen31hoang08minh2003 Countries (BOI06_countries) C++14
100 / 100
3 ms 360 KB
#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_N = 1005, INF = 0X3F3F3F3F, NINF = 0XC0C0C0C0;

class UnsignedFraction {
private:

    long long numerator, denominator;

public:

    UnsignedFraction(const long long numerator, const long long denominator): numerator(numerator), denominator(denominator) {};

    UnsignedFraction(const long long numerator): numerator(numerator), denominator(1) {};

    UnsignedFraction(): numerator(0), denominator(1) {};

    friend bool operator == (const UnsignedFraction &a, const UnsignedFraction &b) {
        return a.numerator * b.denominator == b.numerator * a.denominator;
    }

    friend bool operator > (const UnsignedFraction &a, const UnsignedFraction &b) {
        return a.numerator * b.denominator == b.numerator * a.denominator;
    }

    friend bool operator < (const UnsignedFraction &a, const UnsignedFraction &b) {
        return a.numerator * b.denominator == b.numerator * a.denominator;
    }

    short compare(const UnsignedFraction &other) const {
        const long long first = numerator * other.denominator, second = other.numerator * denominator;
        if (first < second)
            return -1;
        if (first > second)
            return 1;
        return 0;
    }

    UnsignedFraction getReducedFraction() const {
        const long long g = __gcd(this -> numerator, this -> denominator);
        return UnsignedFraction((this -> numerator) / g, (this -> denominator) / g);
    }

    friend ostream& operator << (ostream &outputStream, const UnsignedFraction &fraction) {
        return outputStream << fraction.numerator << '/' << fraction.denominator;
    }

};

char status[MAX_N];
signed capital[MAX_N];
UnsignedFraction maximum[MAX_N];
int n, x[MAX_N], y[MAX_N], s[MAX_N];

/**

    0 <= x[i], y[i], s[i] <= 1000

    s[j] / sqrt(square(x[i] - x[j]) + square(y[i] - y[j])) > s[i]
    => s[j] > s[i] * sqrt(square(x[i] - x[j]) + square(y[i] - y[j]))
    => square(s[j]) > square(s[i]) * (square(x[i] - x[j]) + square(y[i] - y[j]))

**/

long long findSquare(const long long x) {
    return x * x;
}

signed findCapital(const signed c) {
    if (capital[c] == c)
        return c;
    return capital[c] = findCapital(capital[c]);
}

signed main() {

    UnsignedFraction fraction;

    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
//        freopen("output.out", "w", stdout);
    #endif
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i] >> s[i];
        capital[i] = i;
    }

    for (int j = 1, i, flag; j <= n; ++j)
        for (i = 1; i <= n; ++i) {
            if (i == j)
                continue;
            fraction = UnsignedFraction(s[j], findSquare(x[i] - x[j]) + findSquare(y[i] - y[j]));
            flag = maximum[i].compare(fraction);
            if (flag > 0)
                continue;
            if (flag < 0) {
                maximum[i] = fraction;
                capital[i] = j;
            } else
                capital[i] = 0;
        }

    for (int i = 1; i <= n; ++i)
        if (maximum[i].compare(s[i]) <= 0) {
            capital[i] = i;
            status[i] = 'K';
            continue;
        } else if (!capital[i]) {
            capital[i] = i;
            status[i] = 'D';
        }


    for (int i = 1; i <= n; ++i)
        if (status[i])
            cout << status[i] << '\n';
        else
            cout << findCapital(i) << '\n';

    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 360 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 3 ms 340 KB Output is correct