oj.uz

Submission #995049

# Submission time Handle Problem Language Result Execution time Memory
995049 2024-06-08T11:27:03 Z otarius Drzava (COCI15_drzava) C++17
160 / 160
 371 ms 6472 KB 
#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;
          		if (dp[j]) ndp[j] = 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.000001) {
        m = (l + r) / 2;
        if (check(m)) {
            ans = m; r = m;
        } else l = m;
    } cout << setprecision(3) << fixed << ans;
}
int32_t main() {
	int t = 1;
	// cin >> t;
	while (t--) {
		solve();
		cout << '\n';
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 5 ms 2396 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 4 ms 2396 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 4 ms 2500 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 5 ms 2392 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 6 ms 2652 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 70 ms 4444 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 302 ms 6288 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 371 ms 6228 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 235 ms 6012 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 276 ms 5212 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 237 ms 6312 KB Output is correct

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 218 ms 6220 KB Output is correct

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 231 ms 6064 KB Output is correct

Subtask #17
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 235 ms 5452 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 249 ms 5716 KB Output is correct

Subtask #19
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 222 ms 5208 KB Output is correct

Subtask #20
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 223 ms 6472 KB Output is correct