Submission #71639

#TimeUsernameProblemLanguageResultExecution timeMemory
71639mr_bananaTowns (IOI15_towns)C++17
25 / 100
40 ms5520 KiB
#include <bits/stdc++.h> #include "towns.h" using namespace std; const int MN=200,inf=1e9; int dist[MN][MN]; bool mark[MN][MN]; map<int,int> cnt; int n; int getdists(int x){ int mi=0; for(int i=0;i<n;i++){ if(x!=i && !mark[x][i]){ dist[x][i]=dist[i][x]=getDistance(x,i); mark[x][i]=mark[i][x]=1; } if(dist[x][i]>dist[x][mi]){ mi=i; } } return mi; } int hubDistance(int N, int sub) { cnt.clear(); memset(mark,0,sizeof mark); n=N; int u=getdists(0); int v=getdists(u); getdists(v); int ans=inf; for(int i=0;i<n;i++){ int d=(dist[i][v]+dist[i][u]-dist[u][v])/2; cnt[dist[i][v]-d]++; ans=min(ans,max(dist[i][v],dist[i][u])-d); } int n1=0,n2=n; bool f=0; for(auto i:cnt){ if(max(i.first,dist[u][v]-i.first)!=ans){ continue; } n2-=i.second; if(n1<=n/2 && n2<=n2 && i.second<=n/2){ f=1; } n1+=i.second; } if(f){ return ans; } else{ return -ans; } }

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:42:25: warning: self-comparison always evaluates to true [-Wtautological-compare]
         if(n1<=n/2 && n2<=n2 && i.second<=n/2){
                       ~~^~~~
towns.cpp:22:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~
#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...