oj.uz

Submission #253038

# Submission time Handle Problem Language Result Execution time Memory
253038 2020-07-26T17:40:02 Z VEGAnn Drzava (COCI15_drzava) C++14
160 / 160
 432 ms 8952 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
#define i2 array<int,2>
#define i3 array<int,3>
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
const int N = 50100;
const int md = 998244353;
const int PW = 233;
const ld E = 1e-9;
const int K = 33;
const int oo = 2e9;
vector<int> g[N];
set<i2> setik;
set<i2>::iterator iter;
int n, x[N], y[N], vl[N], k, k8, nm[N];
bool mrk[N], ff[K], f[K];

ll sqr(ll x) { return (x * x); }

ll dist(ll x1, ll y1, ll x2, ll y2){
    return sqr(x1 - x2) + sqr(y1 - y2);
}

bool cmp(int _x, int _y){
    return x[_x] < x[_y];
}

void dfs(int v){
    if (f[0]) return;

    mrk[v] = 1;

    fill(ff, ff + K, 0);

    ff[vl[v]] = 1;

    for (int i = 0; i < k; i++)
        if (f[i])
            ff[(i + vl[v]) % k] = 1;

    for (int i = 0; i < k; i++)
        f[i] |= ff[i];

    for (int u : g[v])
        if (!mrk[u])
            dfs(u);
}

bool ok(ll xx){
    for (int i = 0; i < n; i++) {
        g[i].clear();
        mrk[i] = 0;
    }

    setik.clear();

    int root = (int)(trunc(sqrt(xx)));

    for (int it = 0, ptr = 0; it < n; it++){
        int i = nm[it];

        while (ptr < it && sqr(x[i] - x[nm[ptr]]) > xx){
            setik.erase({y[nm[ptr]], nm[ptr]});
            ptr++;
        }

        int cnt = 1;

        for (iter = setik.lower_bound({y[i] - root, -oo}); iter != setik.end(); iter++, cnt++){
            i2 cur = (*iter);

            if (cur[0] > y[i] + root) break;

            if (cnt == k8)
                return 1;

            if (dist(x[i], y[i], x[cur[1]], cur[0]) <= xx){
                g[i].PB(cur[1]);
                g[cur[1]].PB(i);

                if (sz(g[i]) == k - 1)
                    return 1;
            }
        }

        setik.insert({y[i], i});
    }

    for (int i = 0; i < n; i++){
        if (mrk[i]) continue;

        fill(f, f + K, 0);

        dfs(i);

        if (f[0])
            return 1;
    }

    return 0;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> k;

    k8 = (k << 3);

    for (int i = 0; i < n; i++){
        cin >> x[i] >> y[i] >> vl[i];
        vl[i] %= k;
        nm[i] = i;
    }

    sort(nm, nm + n, cmp);

    ll l = 1, r = ll(1e17);

    while (l < r){
        ll md = (l + r) >> 1;

        if (ok(md))
            r = md;
        else l = md + 1;
    }

    cout << fixed << setprecision(3) << sqrt(ld(l));

    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

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

Subtask #5
8.0 / 8.0

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

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 8 ms 1664 KB Output is correct

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 81 ms 2168 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 423 ms 8952 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 432 ms 8824 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 328 ms 5696 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 368 ms 6136 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 351 ms 6264 KB Output is correct

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 230 ms 3380 KB Output is correct

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 263 ms 4088 KB Output is correct

Subtask #17
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 225 ms 4600 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 245 ms 5112 KB Output is correct

Subtask #19
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 268 ms 4088 KB Output is correct

Subtask #20
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 236 ms 3700 KB Output is correct