oj.uz

Submission #155644

# Submission time Handle Problem Language Result Execution time Memory
155644 2019-09-29T14:09:58 Z alexandra_udristoiu Drzava (COCI15_drzava) C++14
160 / 160
 773 ms 29932 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;
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

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

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1540 KB Output is correct
2 Correct 11 ms 1784 KB Output is correct

Subtask #5
8.0 / 8.0

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

Subtask #6
8.0 / 8.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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

Subtask #13
8.0 / 8.0

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

Subtask #14
8.0 / 8.0

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

Subtask #15
8.0 / 8.0

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

Subtask #16
8.0 / 8.0

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

Subtask #17
8.0 / 8.0

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

Subtask #18
8.0 / 8.0

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

Subtask #19
8.0 / 8.0

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

Subtask #20
8.0 / 8.0

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