Submission #155389

#TimeUsernameProblemLanguageResultExecution timeMemory
155389nicolaalexandraDrzava (COCI15_drzava)C++14
0 / 160
1085 ms59568 KiB
/// 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 (stderr)

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++){
                      ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...