Submission #758248

#	Time	Username	Problem	Language	Result	Execution time	Memory
758248		nguyen31hoang08minh2003	Countries (BOI06_countries)	C++14	100 / 100	3 ms	360 KiB

countries

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

• Subtask 1: 100 / 100