oj.uz

Submission #155389

# Submission time Handle Problem Language Result Execution time Memory
155389 2019-09-27T17:53:06 Z nicolaalexandra Drzava (COCI15_drzava) C++14
0 / 160
 1000 ms 59568 KB 
/// vreau sa ma conving ca nu merge asa
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define DIM 50010
#define INF 2000000000
#define EPS 0.00001
using namespace std;
//ifstream cin ("date.in");
//ofstream cout ("date.out");
int n,i,x,y,k;
vector <int> L[DIM],val;
int dp[DIM][33],viz[DIM],cost[DIM];

struct punct {
    int x,y,val,poz;
};
punct v[DIM],d[DIM],w[DIM];
inline int cmp (punct a, punct b){
    if (a.x == b.x){
        if (a.y == b.y)
            return a.val < b.val;
        return a.y < b.y;
    }
    return a.x < b.x;
}
double get_dist (int i, int j, punct v[]){
    return sqrt ( (long double)(v[i].x-v[j].x)*(v[i].x-v[j].x) + (long double)(v[i].y-v[j].y)*(v[i].y-v[j].y) );
}
double modul (double n){
    if (n < 0)
        return -n;
    return n;
}
void uneste (int x, int y){
    L[x].push_back(y);
    L[y].push_back(x);
}
void interclasare (int st, int mid, int dr){
    int i = st, j = mid+1;
    int el = 0;
    while (i <= mid && j <= dr){
        if (v[i].y <= v[j].y){
            d[++el] = v[i];
            i++;
        } else {
            d[++el] = v[j];
            j++;
        }}
    for (;i<=mid;i++)
        d[++el] = v[i];
    for (;j<=dr;j++)
        d[++el] = v[j];
    for (int i=st,j=1;i<=dr;i++,j++)
        v[i] = d[j];
}
double solve (int st, int dr, double max_dist){
    if (st == dr)
        return INF;
    if (st + 1 == dr){
        if (get_dist(st,dr,v) <= max_dist)
            uneste (v[st].poz,v[dr].poz);
        interclasare (st,st,dr);
        return get_dist(st,dr,v);
    }
    /*if (st + 2 == dr){
        double ans = INF*1.0;
        if (get_dist(st,st+1,v) <= max_dist){
            uneste (v[st].poz,v[st+1].poz);
        }
        ans = min (ans,get_dist(st,st+1,v));
        if (get_dist(st,st+2,v) <= max_dist){
            uneste (v[st].poz,v[st+2].poz);
        }
        ans = min (ans,get_dist(st,st+2,v));
        if (get_dist(st+1,st+2,v) <= max_dist){
            uneste (v[st+1].poz,v[st+2].poz);
        }
        ans = min (ans,get_dist(st+1,st+2,v));
        interclasare (st,st,st+1);
        interclasare (st,st+1,dr);
        return ans;
    }*/
    int mid = (st+dr)>>1;
    double ans_st = solve (st,mid,max_dist);
    double ans_dr = solve (mid+1,dr,max_dist);
    interclasare (st,mid,dr);

    double sol = min (ans_st,ans_dr);


    int k = 0;
    for (int i=st;i<=dr;i++)
        if (modul (v[mid].x-v[i].x) <= max_dist) /// sigur iau tle aici
            w[++k] = v[i];

    for (int i=1;i<=k;i++)
        for (int j=i+1;j<=min(k,i+7);j++){
            sol = min (sol,get_dist(i,j,w));
            if (get_dist(i,j,w) <= max_dist)
                uneste (w[i].poz,w[j].poz);
        }
    return sol;
}
void dfs (int nod){
    viz[nod] = 1;
    val.push_back (cost[nod]);
    for (int i=0;i<L[nod].size();i++){
        int vecin = L[nod][i];
        if (!viz[vecin])
            dfs (vecin);
    }}
inline int verif (double max_dist){
    /// initializari
    for (int i=1;i<=n;i++)
        L[i].clear();
    memset (viz,0,sizeof viz);
    sort (v+1,v+n+1,cmp);
    solve (1,n,max_dist);

    for (int i=1;i<=n;i++){
        if (viz[i])
            continue;
        val.clear();
        dfs (i);
        if (val.size() >= k)
            return 1;
        memset (dp,0,sizeof (dp));
        for (int j=0;j<val.size();j++){
            if (!j){
                dp[j][val[j]] = 1;
                continue;
            }
            for (int rest=0;rest<k;rest++){
                if (dp[j-1][rest]){
                    dp[j][rest] = 1;
                    continue;
                }
                int rest_ant = rest-val[j];
                if (rest_ant < 0)
                    rest_ant += k;
                if (dp[j-1][rest_ant])
                    dp[j][rest] = 1;
            }
            dp[j][val[j]] = 1;
        }
        if (dp[val.size()-1][0] == 1)
            return 1;
    }
    return 0;
}
int main (){

    cin>>n>>k;
    for (i=1;i<=n;i++){
        int val;
        cin>>x>>y>>val;
        val %= k;
        v[i] = {x,y,val,i};
        cost[i] = val;
    }
    sort (v+1,v+n+1,cmp);
    double st = 0, dr = 100000000.0, sol = 0;
    while (dr-st >= EPS){
        double mid = (st+dr)/2.0;
        if (verif(mid)){ /// incerc o distanta mai mica
            sol = mid;
            dr = mid;
        } else st = mid;
    }
    cout<<setprecision(3)<<fixed<<sol;


    return 0;
}

Compilation message

drzava.cpp: In function 'void dfs(int)':
drzava.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<L[nod].size();i++){
                  ~^~~~~~~~~~~~~~
drzava.cpp: In function 'int verif(double)':
drzava.cpp:129:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (val.size() >= k)
             ~~~~~~~~~~~^~~~
drzava.cpp:132:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<val.size();j++){
                      ~^~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 8.0

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

Subtask #5
0 / 8.0

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

Subtask #6
0 / 8.0

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

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 8184 KB Output is correct
2 Execution timed out 1065 ms 8784 KB Time limit exceeded

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 8184 KB Output is correct
2 Execution timed out 1072 ms 8568 KB Time limit exceeded

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 8184 KB Output is correct
2 Execution timed out 1083 ms 27324 KB Time limit exceeded

Subtask #10
0 / 8.0

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

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 8212 KB Output is correct
2 Execution timed out 1055 ms 56032 KB Time limit exceeded

Subtask #12
0 / 8.0

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

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 8208 KB Output is correct
2 Execution timed out 1081 ms 59468 KB Time limit exceeded

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 8312 KB Output is correct
2 Execution timed out 1083 ms 59568 KB Time limit exceeded

Subtask #15
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 8184 KB Output is correct
2 Execution timed out 1085 ms 59252 KB Time limit exceeded

Subtask #16
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 8184 KB Output is correct
2 Execution timed out 1084 ms 59400 KB Time limit exceeded

Subtask #17
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 8312 KB Output is correct
2 Execution timed out 1085 ms 59396 KB Time limit exceeded

Subtask #18
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 8184 KB Output is correct
2 Execution timed out 1077 ms 59280 KB Time limit exceeded

Subtask #19
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 8312 KB Output is correct
2 Execution timed out 1078 ms 59384 KB Time limit exceeded

Subtask #20
0 / 8.0

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