Submission #1018575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018575		caterpillow	Drzava (COCI15_drzava)	C++17	64 / 160	96 ms	65536 KiB

drzava

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

struct DSU {
    vt<int> e;
    void init(int n) { e.resize(n, -1); }
    int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (e[x] < e[y]) swap(x, y);
        e[y] += e[x];
        e[x] = y;
        return true;
    }
};

/*

bsearch on D
we can do a bitmask knapsack to check in O(fast)

idk how to build the connected components fast

*/

using db = long double;
using pd = pair<db, db>;
using t3 = tuple<db, int, int>;

int n, k;
vt<int> v;
vt<pd> pts;
vt<t3> edges;

#define sq(x) ((x) * (x))
db dist(pd a, pd b) {
    return sqrtl(sq(a.f - b.f) + sq(a.s - b.s));
}

void process() {
    cin >> n >> k;
    v.resize(n);
    pts.resize(n);
    F0R (i, n) {
        db x, y; ll pop;
        cin >> x >> y >> pop;
        pts[i] = {x, y};
        v[i] = pop % k;
    }

    vt<t3> poss;
    F0R (i, n) {
        FOR (j, i + 1, n) {
            poss.pb({dist(pts[i], pts[j]), i, j});
        }
    }
    sort(all(poss));
    DSU dsu; 
    dsu.init(n);
    for (auto [w, u, v] : poss) {
        if (dsu.unite(u, v)) {
            edges.pb({w, u, v});
        }
    }
}

void add_weight(ll& dp, ll w) {
    dp |= dp << w;
    dp |= dp >> k;
}

bool check(db d) {
    DSU dsu;
    dsu.init(n);
    for (auto [w, u, v] : edges) {
        if (w > d) break;
        dsu.unite(u, v);
    }
    vt<ll> msks(n, 1);
    F0R (u, n) {
        int rep = dsu.find(u);
        add_weight(msks[rep], v[u]);
    }
    F0R (i, n) {
        if (1 & (msks[i] >> k)) return true;
    }
    return false;
} 

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    process();

    const db eps = 1e-6;
    db lo = 0, hi = 1e9;
    while (hi - lo > eps) {
        db m = (lo + hi) / 2;
        if (check(m)) hi = m;
        else lo = m;
    }
    cout << fixed << setprecision(3) << hi << endl;
}

Compilation message (stderr)

drzava.cpp:133:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  133 | main() {
      | ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 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