Submission #1234206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234206		caterpillow	Drzava (COCI15_drzava)	C++17	160 / 160	449 ms	39032 KiB

drzava

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll inf = 1e9;

struct DSU {
	vector<int> e; 
	void init(int n) { 
		e.resize(n, -1);
	}
	int operator[](int x) { 
		return e[x] < 0 ? x : e[x] = (*this)[e[x]]; 
	}   
	bool operator()(int x, int y) {
		x = (*this)[x], y = (*this)[y]; 
		if (x == y) return 0;
		if (e[x] > e[y]) swap(x,y);
		e[x] += e[y]; 
		e[y] = x; 
		return 1;
	}
	// optional
	bool same_set(int a, int b) { return (*this)[a] == (*this)[b]; }
	int sz(int x) { return -e[(*this)[x]]; }
	int add() { e.push_back(-1); return size(e) - 1; }
};

using P = array<int, 3>;
struct Node {
    #define _sq(x) (x) * (x)
    P lo, hi;
    struct Node *lc, *rc;

    ll dist2(const P &a, const P &b) const { 
        return 1ll * _sq(a[0] - b[0]) + 1ll * _sq(a[1] - b[1]); 
    }

    ll dist2(P &p) {
		#define _loc(i) (p[i] < lo[i] ? lo[i] : (p[i] > hi[i] ? hi[i] : p[i]))
		return dist2(p, {_loc(0), _loc(1)});
    }

    template<class ptr>
    Node (ptr l, ptr r, int d) : lc(0), rc(0) {
        lo = {inf, inf, inf}, hi = {-inf, -inf, -inf};
        for (ptr p = l; p < r; p++) {
            for (int i = 3; i--;) lo[i] = min(lo[i], (*p)[i]), hi[i] = max(hi[i], (*p)[i]);
        }
        if (r - l == 1) return;
        ptr m = l + (r - l) / 2;
        nth_element(l, m, r, [&] (auto a, auto b) { return a[d] < b[d]; });
        lc = new Node(l, m, d ^ 1);
        rc = new Node(m, r, d ^ 1);
    }

    void search(P p, priority_queue<pair<ll, int>> &pq) {
        if (lc) {
            ll dl = lc->dist2(p), dr = rc->dist2(p);
            if (dl > dr) swap(lc, rc), dr = dl;
            lc->search(p, pq);
            if (dr < pq.top().first) rc->search(p, pq);
        } else pq.push({dist2(p, lo), lo[2]}), pq.pop();
    }
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int n, k;
	cin >> n >> k;
    vector<P> pts(n);
    vector<ll> w(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i][0] >> pts[i][1] >> w[i];
        w[i] %= k;
        pts[i][2] = i;
    }
    Node node(pts.begin(), pts.end(), 0);

    vector<tuple<ll, int, int>> candidate_edges, edges;
    for (int i = 0; i < n; i++) {
        int id = pts[i][2];
        priority_queue<pair<ll, int>> pq;
        for (int j = k; j--;) pq.push({inf * inf, -1});
        node.search(pts[i], pq);
        while (pq.size()) {
            auto [dist, id0] = pq.top(); pq.pop();
            if (id0 == -1) continue;
            candidate_edges.push_back({dist, id, id0});
        }
    }
    sort(candidate_edges.begin(), candidate_edges.end());
    DSU dsu;
    dsu.init(n);
    for (auto [dist, u, v] : candidate_edges) {
        if (dsu(u, v)) edges.push_back({dist, u, v});
    }
    ll lo = 0, hi = inf * inf;
    while (hi - lo > 1) {
        ll m = (lo + hi) / 2;

        DSU dsu;
        dsu.init(n);
        for (auto [dist, u, v] : edges) {
            if (dist > m) break;
            dsu(u, v);
        }
        vector<ll> msk(n, 1);
        int good = 0;
        for (int i = 0; i < n; i++) {
            int j = dsu[i];
            msk[j] |= (msk[j] << w[i]);
            msk[j] |= msk[j] >> k;
            good |= 1 & (msk[j] >> k);
        }
        if (good) hi = m;
        else lo = m;
    }
    cout << fixed << setprecision(3) << sqrtl(hi) << '\n';
}

• 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: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8
• Subtask 13: 8 / 8
• Subtask 14: 8 / 8
• Subtask 15: 8 / 8
• Subtask 16: 8 / 8
• Subtask 17: 8 / 8
• Subtask 18: 8 / 8
• Subtask 19: 8 / 8
• Subtask 20: 8 / 8