Submission #1230769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230769		Matthewwww	Drzava (COCI15_drzava)	C++17	120 / 160	1096 ms	37188 KiB

drzava

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif

struct Dsu {
	vector<int> par;
	vector<vector<int>> chd;
	Dsu (int N): par(N, -1), chd(N) {}
	inline int fpar (int x) { return par[x] < 0 ? x : par[x] = fpar(par[x]);}
	inline int merge (int x, int y) {
		if ((x = fpar(x)) == (y = fpar(y))) return -1;
		if (par[x] < par[y]) swap(x, y);
		par[y] += par[x];
		par[x] = y;
		chd[y].push_back(x);
		return y;
	}
	inline void get (int i, vector<int> &vt) {
		vt.push_back(i);
		for (int j: chd[i]) get(j, vt);
	}
};

inline ll d2 (pair<int, int> a, pair<int, int> b) { return (ll)(a.f-b.f)*(ll)(a.f-b.f)+(ll)(a.s-b.s)*(ll)(a.s-b.s);}
inline int isqrt (ll x) { return (int)sqrt(x);}

bool check (vector<int> vt, int k) {
	vector<bool> dp(k, 0);
	for (int i: vt) {
		vector<bool> pd = dp;
		dp[i%k] = true;
		for (int j = 0; j < k; j++) if (pd[j]) dp[(j+i)%k] = true;
	}
	return dp[0];
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k;
	cin >> n >> k;
	vector<pair<pair<int, int>, int>> raw(n);
	vector<pair<int, int>> vt(n);
	vector<int> w(n);
	for (auto &i: raw) cin >> i.f.f >> i.f.s >> i.s;
	sort(raw.begin(), raw.end());
	for (int i = 0; i < n; i++) {
		vt[i] = raw[i].f;
		w[i] = raw[i].s;
	}
	vector<pair<ll, pair<int, int>>> edges;
	set<pair<int, int>> st; // y then index
	priority_queue<pair<int, int>> pq; // x then index
	ll len = 1e18;
	for (int i = 0; i < n; i++) {
		auto l = st.lower_bound({vt[i].s-isqrt(len), -1});
		auto r = st.upper_bound({vt[i].s+isqrt(len), n});
		vector<pair<ll, int>> dt;
		for (auto it = l; it != r; ++it) dt.push_back({d2(vt[i], vt[(*it).s]), (*it).s});
		sort(dt.begin(), dt.end());
		if (dt.size() >= k-1) {
			for (int j = 0; j < k-1; j++) edges.push_back({dt[j].f, {dt[j].s, i}});
			len = min(len, dt[k-2].f);
		} else {
			for (auto j: dt) edges.push_back({j.f, {j.s, i}});
		}
		while (pq.size() && pq.top().f < vt[i].f-isqrt(len)) {
			st.erase({vt[pq.top().s].s, pq.top().s});
			pq.pop();
		}
		pq.push({vt[i].f, i});
		st.insert({vt[i].s, i});
	}
	sort(edges.begin(), edges.end());
	Dsu dsu(n);
	for (auto i: edges) err << i.f << " " << i.s.f << " " << i.s.s << "\n";
	for (auto i: edges) {
		int rt = dsu.merge(i.s.f, i.s.s);
		if (!~rt) continue;
		vector<int> v;
		dsu.get(rt, v);
		vector<int> vn;
		for (int j: v) vn.push_back(w[j]);
		if (check(vn, k)) return cout << fixed << setprecision(3) << sqrt(i.f) << "\n", 0;
	}
}

• 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: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8
• Subtask 13: 0 / 8
• Subtask 14: 0 / 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