| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 995041 | otarius | Drzava (COCI15_drzava) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define sc second
#define pb push_back
#define int long long
#define pii pair<int, int>
bool dp[50005][31];
vector<int> vec[50005];
int n, k, par[50005], sz[50005];
vector<pair<pii, int>> v;
int dist(pii x, pii y) {
return (x.ff - y.ff) * (x.ff - y.ff) + (x.sc - y.sc) * (x.sc - y.sc);
}
void make_set() {
for (int i = 1; i <= n; i++) {
par[i] = i; sz[i] = 1; vec[i].clear();
}
}
int find_set(int v) {
if (par[v] == v)
return v;
return par[v] = find_set(par[v]);
}
void union_set(int x, int y) {
x = find_set(x);
y = find_set(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
par[y] = x; sz[x] += sz[y];
}
bool check(double d) {
make_set();
set<pii> st; int j = 1;
for (int i = 1; i <= n; i++) {
while (j < i && v[i].ff.ff - v[j].ff.ff > d) {
st.erase({v[j].ff.sc, j}); j++;
} auto it = st.lower_bound({v[i].ff.sc - d, -1});
for ( ; it != st.end() && (*it).ff <= v[i].ff.sc + d; it++) {
if (dist(v[i].ff, v[(*it).sc].ff) <= d * d) {
union_set(i, (*it).sc);
if (sz[find_set(i)] >= k) { return 1; }
}
} st.insert({v[i].ff.sc, i});
} for (int i = 1; i <= n; i++)
vec[find_set(i)].pb(i);
for (int i = 1; i <= n; i++) {
if (vec[i].size() == 0) continue;
vector<bool> dp(k, 0), ndp(k, 0);
for (int u : vec[i]) {
ndp[v[u].sc % k] = 1;
for (int j = 0; j < k; j++)
if (dp[j]) ndp[(j + v[u].sc) % k] = 1;
dp = ndp;
for (int j = 0; j < k; j++) ndp[j] = 0;
} if (dp[0]) { return 1; }
} return 0;
}
void solve() {
cin >> n >> k;
v.resize(n + 5);
for (int i = 1; i <= n; i++)
cin >> v[i].ff.ff >> v[i].ff.sc >> v[i].sc;
sort(v.begin() + 1, v.begin() + n + 1);
double l = 0, r = 2 * 1e8, m, ans;
while (r - l > 0.0001) {
m = (l + r) / 2;
if (check(m)) {
ans = m; r = m;
} else l = m;
} cout << setprecision(3) << fixed << ans;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
cout << '\n';
}
}