Submission #253811

#	Time	Username	Problem	Language	Result	Execution time	Memory
253811		Vimmer	Drzava (COCI15_drzava)	C++14	0 / 160	4 ms	2816 KiB

drzava

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define pf push_front
#define N 50050
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef short int si;
typedef array <ll, 3> a3;
typedef array <ll, 5> a5;

//typedef tree <ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


int n, k, kol[N], pr[N], id;

ld x[N], y[N];

multiset <int> se[N];

bool f[N][35];

void make(int x) {pr[x] = x; se[x].clear(); se[x].insert(kol[x]);}

int fnd(int x) {if (pr[x] != x) pr[x] = fnd(pr[x]); return pr[x];}

void link(int a, int b)
{
    if (sz(se[a]) < sz(se[b])) swap(a, b);

    pr[b] = a;

    for (auto it : se[b]) se[a].insert(it);
}

ld dist(int a, int b) {return sqrt(pow(x[a] - x[b], 2) + pow(y[a] - y[b], 2));}

bool can(ld x)
{
    id++;

    for (int i = 0; i < n; i++) make(i);

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
        {
            int a = fnd(i), b = fnd(j);

            if (a == b) continue;

            if (x - dist(i, j) >= 0.0001)
                link(a, b);
        }

    set <int> st; st.clear();

    for (int i = 0; i < n; i++) st.insert(fnd(i));

    for (auto it : st)
    {
        vector <int> vals; vals.clear();

        for (auto itr : se[it]) vals.pb(itr);

        f[1][vals[0]] = id;

        if (vals[0] == 0) return 1;

        for (int i = 1; i < sz(vals); i++)
          for (int j = 0; j < k; j++)
            if (f[i][j] == id || j == 0)
            {
                f[i + 1][j] = id;

                int nval = (j + vals[i]) % k;

                if (nval == 0) return 1;

                f[i + 1][nval] = id;
            }
    }

    return 0;
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> k;

    for (int i = 0; i < n; i++) {cin >> x[i] >> y[i] >> kol[i]; kol[i] %= k;}

    ld l = 0, r = 100000000;

    while (r - l >= 0.0001)
    {
        ld md = (r + l) * 0.5;

        if (can(md)) r = md; else l = md;
    }

    cout << setprecision(3) << fixed;

    cout << l << endl;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 8
• Subtask 5: 0 / 8
• Subtask 6: 0 / 8
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8
• Subtask 13: 0 / 8
• Subtask 14: 0 / 8
• Subtask 15: 0 / 8
• Subtask 16: 0 / 8
• Subtask 17: 0 / 8
• Subtask 18: 0 / 8
• Subtask 19: 0 / 8
• Subtask 20: 0 / 8