Submission #697609

#	Time	Username	Problem	Language	Result	Execution time	Memory
697609		finn__	Countries (BOI06_countries)	C++17	100 / 100	191 ms	368 KiB

countries

#include <bits/stdc++.h>
using namespace std;

struct DSU
{
    vector<int64_t> y;

    DSU(size_t n) { y = vector<int64_t>(n, -1); }

    int64_t representative(int64_t u)
    {
        return y[u] < 0 ? u : (y[u] = representative(y[u]));
    }

    void unite(int64_t u, int64_t v)
    {
        u = representative(u), v = representative(v);
        if (u != v)
            y[v] = u;
    }
};

typedef pair<int, int> fraction;

fraction reduce_fraction(fraction const f)
{
    int g = __gcd(f.first, f.second);
    return {f.first / g, f.second / g};
}

long double val(fraction const &f)
{
    return (long double)f.first / (long double)f.second;
}

bool compare_influence(pair<int, fraction> const &f, pair<int, fraction> const &g)
{
    return ((long double)f.second.first / (long double)f.second.second) <
           ((long double)g.second.first / (long double)g.second.second);
}

int main()
{
    size_t n;
    cin >> n;

    vector<complex<int>> cities(n);
    vector<int> s(n);
    for (size_t i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y >> s[i];
        cities[i] = {x, y};
    }

    DSU dsu(n);
    vector<string> ans(n);

    for (size_t i = 0; i < n; i++)
    {
        vector<pair<unsigned, fraction>> influence;
        for (size_t j = 0; j < n; j++)
            if (i != j)
                influence.emplace_back(j, reduce_fraction({s[j], norm(cities[j] - cities[i])}));
        sort(influence.begin(), influence.end(), compare_influence);

        if (s[i] * influence.back().second.second >= influence.back().second.first)
            ans[i] = "K\n";
        else if (influence.size() >= 2 && influence.back().second == influence[influence.size() - 2].second)
            ans[i] = "D\n";
        else
            dsu.unite(influence.back().first, i);
    }

    for (size_t i = 0; i < n; i++)
        if (dsu.representative(i) != i)
            ans[i] = to_string(dsu.representative(i) + 1) + "\n";
    for (string const &x : ans)
        cout << x;
}

Compilation message (stderr)

countries.cpp: In function 'int main()':
countries.cpp:76:35: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if (dsu.representative(i) != i)
      |             ~~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 100 / 100