# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
71639 | 2018-08-25T09:32:11 Z | mr_banana | Towns (IOI15_towns) | C++17 | 40 ms | 5520 KB |
#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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 1016 KB | Output is correct |
2 | Correct | 22 ms | 1712 KB | Output is correct |
3 | Correct | 3 ms | 1712 KB | Output is correct |
4 | Correct | 31 ms | 2176 KB | Output is correct |
5 | Correct | 31 ms | 2840 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 2840 KB | Output is correct |
2 | Correct | 29 ms | 3244 KB | Output is correct |
3 | Correct | 39 ms | 3828 KB | Output is correct |
4 | Correct | 28 ms | 4364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 4884 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 40 ms | 5392 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 22 ms | 5520 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 5520 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |