#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int n,dist[111][111],u,v,R,sz[2],p[111];
int d(int u, int v){
if (u==v)
return 0;
if (u>v)
swap(u,v);
if (dist[u][v])
return dist[u][v];
return dist[u][v]=getDistance(u,v);
}
int f(int i){
return (p[i]==i?i:p[i]=f(p[i]));
}
void unite(int i, int j){
p[f(j)]=f(i);
}
bool check(int i, int j){
int x=(d(i,u)+d(i,v)-d(u,v))/2,y=(d(j,u)+d(j,v)-d(u,v))/2;
return (d(i,j)<x+y);
}
int calc(vector <int> a){
if (a.empty())
return -1;
if (a.size()==1)
return a[0];
vector <int> ve;
for (int i=0;i+1<a.size();i+=2)
if (check(a[i],a[i+1])){
unite(a[i],a[i+1]);
ve.push_back(a[i]);
}
if (a.size()&1)
ve.push_back(a.back());
return calc(ve);
}
int hubDistance(int N, int sub){
n=N;
iota(p,p+n,0);
memset(dist,0,sizeof(dist));
pair <int, int> mx={0,-1};
for (int i=0;i<n;i++)
mx=max(mx,{d(0,i),i});
u=mx.second;
mx={0,-1};
for (int i=0;i<n;i++)
mx=max(mx,{d(u,i),i});
v=mx.second,R=1e9,sz[0]=sz[1]=0;
for (int i=0;i<n;i++)
R=min(R,abs(d(i,u)-d(i,v)));
vector <int> a,b,tmp;
for (int i=0;i<n;i++){
int val=d(i,u)-d(i,v);
if (val<-R)
sz[0]++;
if (val==-R)
a.push_back(i);
if (val==R)
b.push_back(i);
if (val>R)
sz[1]++;
}
if (!R)
b.clear();
R=(R+d(u,v))/2;
if (max(max(sz[0],sz[1]),(int)min(sz[1]+b.size(),sz[0]+a.size()))>n/2)
return -R;
if (min(max(a.size(),sz[1]+b.size()),max(b.size(),sz[0]+a.size()))<=n/2)
return R;
if (b.size()+sz[1]>n/2)
swap(a,b);
int w=calc(a),cnt=0;
if (w==-1)
return R;
for (int i:a)
if (i!=w&&i==f(i))
if (check(w,i))
unite(w,i);
for (int i:a)
cnt+=(f(i)==w);
return (cnt>n/2?-R:R);
}
Compilation message
towns.cpp: In function 'int d(int, int)':
towns.cpp:5:18: warning: declaration of 'v' shadows a global declaration [-Wshadow]
5 | int d(int u, int v){
| ~~~~^
towns.cpp:4:24: note: shadowed declaration is here
4 | int n,dist[111][111],u,v,R,sz[2],p[111];
| ^
towns.cpp:5:11: warning: declaration of 'u' shadows a global declaration [-Wshadow]
5 | int d(int u, int v){
| ~~~~^
towns.cpp:4:22: note: shadowed declaration is here
4 | int n,dist[111][111],u,v,R,sz[2],p[111];
| ^
towns.cpp: In function 'int calc(std::vector<int>)':
towns.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i=0;i+1<a.size();i+=2)
| ~~~^~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:70:71: warning: comparison of integer expressions of different signedness: 'const long unsigned int' and 'int' [-Wsign-compare]
70 | if (min(max(a.size(),sz[1]+b.size()),max(b.size(),sz[0]+a.size()))<=n/2)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
towns.cpp:72:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | if (b.size()+sz[1]>n/2)
| ~~~~~~~~~~~~~~^~~~
towns.cpp:39:28: warning: unused parameter 'sub' [-Wunused-parameter]
39 | int hubDistance(int N, int sub){
| ~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
348 KB |
Output is correct |
2 |
Correct |
8 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
12 ms |
528 KB |
Output is correct |
5 |
Correct |
12 ms |
536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
532 KB |
Output is correct |
2 |
Incorrect |
11 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
344 KB |
Output is correct |
2 |
Incorrect |
13 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |