oj.uz

Submission #697609

# Submission time Handle Problem Language Result Execution time Memory
697609 2023-02-10T14:43:37 Z finn__ Countries (BOI06_countries) C++17
100 / 100
 191 ms 368 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 6 ms 212 KB Output is correct
3 Correct 14 ms 304 KB Output is correct
4 Correct 24 ms 316 KB Output is correct
5 Correct 42 ms 320 KB Output is correct
6 Correct 56 ms 344 KB Output is correct
7 Correct 88 ms 344 KB Output is correct
8 Correct 124 ms 340 KB Output is correct
9 Correct 146 ms 364 KB Output is correct
10 Correct 191 ms 368 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 7 ms 320 KB Output is correct
13 Correct 16 ms 304 KB Output is correct
14 Correct 24 ms 212 KB Output is correct
15 Correct 45 ms 340 KB Output is correct
16 Correct 65 ms 304 KB Output is correct
17 Correct 89 ms 344 KB Output is correct
18 Correct 95 ms 352 KB Output is correct
19 Correct 107 ms 340 KB Output is correct
20 Correct 186 ms 368 KB Output is correct