oj.uz

Submission #155215

# Submission time Handle Problem Language Result Execution time Memory
155215 2019-09-27T06:52:17 Z alexandra_udristoiu Drzava (COCI15_drzava) C++14
16 / 160
 339 ms 3320 KB 
#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;
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(double d){
    int i, j, u, nr;
    set< pair<int, int> > :: iterator it;
    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) );
        it = s.lower_bound( make_pair(v[i].y, i) );
        nr = 0;
        while(it != s.begin()){
            it--;
            nr++;
            if(nr == 4 * k){
                return 1;
            }
            if( dist(it->second, i) <= d * d ){
                vec[i].push_back(it->second);
                vec[it->second].push_back(i);
            }
        }
        it = s.lower_bound( make_pair(v[i].y, i) );
        it++;
        nr = 0;
        while(it != s.end()){
            nr++;
            if(nr == 4 * k){
                return 1;
            }
            if( dist(it->second, i) <= d * d ){
                vec[i].push_back(it->second);
            }
            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 = 100;
    dr = 2000000000000LL;
    while(st <= dr){
        mid = (st + dr) / 2;
        r = mid / 10000.0;
        if( solve(r) ){
            dr = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }
    if(st % 10 >= 5){
        st += 10;
    }
    st /= 10;
    r = st / 1000.0;
    cout<< setprecision(3) << fixed << r;
    return 0;
}

Compilation message

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Incorrect 4 ms 1528 KB Output isn't correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

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

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Incorrect 4 ms 1528 KB Output isn't correct

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1532 KB Output is correct
2 Incorrect 4 ms 1528 KB Output isn't correct

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Incorrect 5 ms 1528 KB Output isn't correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Incorrect 5 ms 1528 KB Output isn't correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Incorrect 41 ms 2400 KB Output isn't correct

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Incorrect 86 ms 3320 KB Output isn't correct

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1504 KB Output is correct
2 Incorrect 339 ms 2872 KB Output isn't correct

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Incorrect 84 ms 3092 KB Output isn't correct

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1448 KB Output is correct
2 Incorrect 88 ms 2984 KB Output isn't correct

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Incorrect 87 ms 2316 KB Output isn't correct

Subtask #15
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Incorrect 87 ms 2308 KB Output isn't correct

Subtask #16
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Incorrect 86 ms 2312 KB Output isn't correct

Subtask #17
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Incorrect 86 ms 2268 KB Output isn't correct

Subtask #20
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Incorrect 86 ms 2392 KB Output isn't correct