Submission #685425

#	Time	Username	Problem	Language	Result	Execution time	Memory
685425		socpite	Drzava (COCI15_drzava)	C++17	160 / 160	91 ms	2864 KiB

drzava

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