oj.uz

Submission #155390

# Submission time Handle Problem Language Result Execution time Memory
155390 2019-09-27T18:01:58 Z alexandra_udristoiu Drzava (COCI15_drzava) C++14
120 / 160
 1000 ms 51952 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;
    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--;
            if(v[i].y - it->first > d){
                break;
            }
            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()){
            if(it->first - v[i].y > d){
                break;
            }
            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++;
        }
    }
    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 = 10000;
    dr = 20000000000000LL;
    while(st <= dr){
        mid = (st + dr) / 2;
        r = mid / 100000.0;
        if( solve(r) ){
            dr = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }
    if(st % 100 >= 50){
        st += 100;
    }
    st /= 100;
    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
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 #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1532 KB Output is correct
2 Correct 12 ms 1912 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 12 ms 2040 KB Output is correct

Subtask #6
8.0 / 8.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1508 KB Output is correct
2 Correct 15 ms 2168 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 11 ms 1784 KB Output is correct

Subtask #9
8.0 / 8.0

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

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1532 KB Output is correct
2 Execution timed out 1045 ms 49828 KB Time limit exceeded

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1532 KB Output is correct
2 Execution timed out 1067 ms 48000 KB Time limit exceeded

Subtask #12
8.0 / 8.0

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

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Execution timed out 1062 ms 51952 KB Time limit exceeded

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Execution timed out 1046 ms 51948 KB Time limit exceeded

Subtask #15
8.0 / 8.0

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

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 577 ms 9976 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 505 ms 14924 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 548 ms 14656 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 554 ms 8804 KB Output is correct

Subtask #20
8.0 / 8.0

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