Submission #155644

#	Time	Username	Problem	Language	Result	Execution time	Memory
155644		alexandra_udristoiu	Drzava (COCI15_drzava)	C++14	160 / 160	773 ms	29932 KiB

drzava

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<iomanip>
#define DIM 50005
using namespace std;
int n, k, i;
long long st, dr, mid;
long double r;
int viz[DIM], a[35], b[35];
vector<int> vec[DIM];
set< pair<int, int> > s;
struct str{
    int x, y, c;
};
str v[DIM];
int cmp(str a, str b){
    if(a.x == b.x){
        return a.y < b.y;
    }
    return a.x < b.x;
}
long long dist(int i, int j){
    return (v[i].x - v[j].x) * 1LL * (v[i].x - v[j].x) + (v[i].y - v[j].y) * 1LL * (v[i].y - v[j].y);
}
void dfs(int nod){
    int i, vecin;
    viz[nod] = 1;
    for(i = 0; i < k; i++){
        b[i] = a[i];
        if(i - v[nod].c >= 0 && a[i - v[nod].c] == 1){
            b[i] = 1;
        }
        if(i - v[nod].c < 0 && a[i - v[nod].c + k] == 1){
            b[i] = 1;
        }
    }
    b[ v[nod].c ] = 1;
    for(i = 0; i < k; i++){
        a[i] = b[i];
    }
    for(i = 0; i < vec[nod].size(); i++){
        vecin = vec[nod][i];
        if(viz[vecin] == 0){
            dfs(vecin);
        }
    }
}
int solve(long double d){
    int i, j, u, nr;
    set< pair<int, int> > :: iterator it, it2;
    for(i = 1; i <= n; i++){
        vec[i].clear();
        viz[i] = 0;
    }
    u = 1;
    for(i = 1; i <= n; i++){
        while(v[i].x - v[u].x > d){
            s.erase( make_pair(v[u].y, u) );
            u++;
        }
        s.insert( make_pair(v[i].y, i) );
        it2 = it = s.lower_bound( make_pair(v[i].y, i) );
        nr = 0;
        while(it != s.begin()){
            it--;
            if(v[i].y - it->first > d){
                break;
            }
            nr++;
            if(nr == 4 * k - 3){
                return 1;
            }
            if( dist(it->second, i) <= d * d ){
                vec[i].push_back(it->second);
                vec[it->second].push_back(i);
            }
        }
        it = it2;
        it++;
        nr = 0;
        while(it != s.end()){
            if(it->first - v[i].y > d){
                break;
            }
            nr++;
            if(nr == 4 * k - 3){
                return 1;
            }
            if( dist(it->second, i) <= d * d ){
                vec[i].push_back(it->second);
                vec[it->second].push_back(i);
            }
            it++;
        }
    }
    for(i = n; i >= 1; i--){
        if(viz[i] == 0){
            for(j = 0; j < k; j++){
                a[j] = 0;
            }
            dfs(i);
            if(a[0] == 1){
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    cin>> n >> k;
    for(i = 1; i <= n; i++){
        cin>> v[i].x >> v[i].y >> v[i].c;
        v[i].c %= k;
    }
    sort(v + 1, v + n + 1, cmp);
    st = 1000;
    dr = 150000000000LL;
    while(st <= dr){
        mid = (st + dr) / 2;
        r = mid / 1000.0;
        if( solve(r) ){
            dr = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }
    if(solve(st / 1000.0 - 0.0005) == 1){
        st--;
    }
    r = st / 1000.0;
    cout<< setprecision(3) << fixed << r;
    return 0;
}

Compilation message (stderr)

drzava.cpp: In function 'void dfs(int)':
drzava.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i < vec[nod].size(); i++){
                ~~^~~~~~~~~~~~~~~~~

• 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