oj.uz

Submission #685425

# Submission time Handle Problem Language Result Execution time Memory
685425 2023-01-24T10:40:06 Z socpite Drzava (COCI15_drzava) C++17
160 / 160
 91 ms 2864 KB 
#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 5e4+5;

int n, k;

ll l = 1, r = 1e18, q_mid;

pair<int, int> A[maxn];
unsigned int org[maxn], C[maxn];

bool found = 0;

int a1[maxn], a2[maxn], tmp1[maxn], tmp2[maxn], up[maxn];

int Find(int x){
    if(up[x] == -1)return x;
    else return up[x] = Find(up[x]);
}

void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    if(a == b)return;
    int tmp = C[a];
    for(int i = 1; i < k; i++){
        if(C[b]&(1<<i))tmp|=(C[a]<<i)|(C[a]>>(k-i));
    }
    C[a] = tmp|C[b];
    C[a]&=(1<<k)-1;
    //cout << a << " " << b << "\n" << C[a] << "\n";
    if(C[a]&1)found = 1;
    up[b] = a;
}

void dist(int a, int b){
    if(1LL*(A[a].f - A[b].f)*(A[a].f - A[b].f) + 1LL*(A[a].s - A[b].s)*(A[a].s - A[b].s) <= q_mid)Union(a, b);
}

bool cmp1(int a, int b){
    return A[a].f < A[b].f;
}

bool cmp2(int a, int b){
    return A[a].s < A[b].s;
}

void solve(int l, int r){
    if(l+1 == r)a2[l] = a1[l];
    else{
        int mid = (l+r)>>1;
        solve(l, mid);
        if(found)return;
        solve(mid, r);
        //cout << "solve " << l << " " << r << "\n";
        if(found)return;
        int sz1 = 0, sz2 = 0;
        int md = A[a1[mid]].f;
        for(int i = l; i < mid; i++)if(1LL*(md - A[a2[i]].f)*(md - A[a2[i]].f) <= q_mid)tmp1[sz1++] = a2[i];
        for(int i = mid; i < r; i++)if(1LL*(md - A[a2[i]].f)*(md - A[a2[i]].f) <= q_mid)tmp2[sz2++] = a2[i];
        int ptr = 0;
        for(int i = 0; i < sz1; i++){
            while(ptr < sz2 && A[tmp2[ptr]].s < A[tmp1[i]].s && 1LL*(A[tmp2[ptr]].s - A[tmp1[i]].s)*(A[tmp2[ptr]].s - A[tmp1[i]].s) > q_mid)ptr++;
            int cptr = ptr;
            //cout << "ptr " << i << " " << ptr << "\n";
            while(cptr < sz2 && 1LL*(A[tmp2[cptr]].s - A[tmp1[i]].s)*(A[tmp2[cptr]].s - A[tmp1[i]].s) <= q_mid){
                dist(tmp1[i], tmp2[cptr++]);
                if(found)break;
            }
            if(found)break;
        }
        if(found)return;
        merge(a2+l, a2+mid, a2+mid, a2+r, tmp1+l, cmp2);
        for(int i = l; i < r; i++)a2[i] = tmp1[i];
    }
}

bool chk(){
    found = 0;
    for(int i = 0; i < n; i++){
        up[i] = -1;
        C[i] = 1<<org[i];
    }
    solve(0, n);
    return found;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> A[i].f >> A[i].s >> org[i];
        org[i]%=k;
        a1[i]=i;
    }
    sort(a1, a1+n, cmp1);
    while(l < r){
        q_mid = (l+r)>>1;
        if(chk())r = q_mid;
        else l = q_mid+1;
    }
    cout << setprecision(3) << fixed << sqrt(l);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

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

Subtask #5
8.0 / 8.0

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

Subtask #6
8.0 / 8.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 28 ms 1620 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 74 ms 2864 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 91 ms 2844 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 54 ms 2564 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 56 ms 2824 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 60 ms 2788 KB Output is correct

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 43 ms 2784 KB Output is correct

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 53 ms 2736 KB Output is correct

Subtask #17
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 38 ms 2564 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 42 ms 2576 KB Output is correct

Subtask #19
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 33 ms 2632 KB Output is correct

Subtask #20
8.0 / 8.0

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