#include "towns.h"
#include<stdlib.h>
int z;
int cache[120][120];
int l(int i, int j){return i<j?i:j;}
int h(int i, int j){return i>j?i:j;}
int ask(int i, int j) { if(cache[i][j]>=0)return cache[i][j];return cache[i][j]=cache[j][i]=(i-j ? getDistance(i, j): 0); }
int argmax(int x, int N) {
int mx = 0, dist = -1;
for (int y, i = 0; i < N; ++i)
if (dist < (y = ask(x, i)))
dist = y, mx = i, z = dist;
return mx;
}
#include<map>
/* each branch store [arbitary node, branch length (to that node), count of leaves node in branch] */
std::map<int,std::vector<std::array<int,3>>>M;
int hubDistance(int N, int sub) {
memset(cache,-1,sizeof cache);
if (sub==1){
int d1 = argmax(0, N);
int d2 = argmax(d1, N);
int dd = z;
int R = 1e9;
for (int i = 0; i < N; ++i) {
int a=ask(d1,i),b=ask(d2,i);
int branch = (a+b-dd)/2;
if(h(a,b)-branch<R)
M.clear(),R=h(a,b)-branch;
if(h(a,b)-branch==R)
++M[a];
R=l(R,h(a,b)-branch);
}
return R;
}else if(sub==3){
int d1 = argmax(0, N);
int d2 = argmax(d1, N);
int dd = z;
for(int i=0;i<N;++i)for(int j=0;j<N;++j)ask(i,j);
int R = 1e9;
for (int i = 0; i < N; ++i) {
int a=ask(d1,i),b=ask(d2,i);
int branch = (a+b-dd)/2;
if(h(a,b)-branch<R){
M.clear(),R=h(a,b)-branch;
M[a].push_back(std::array<int,3>{i,branch, 1});
}
else if(h(a,b)-branch==R){
int found=0;
for(auto &x:M[a])
if(ask(x[0],i)<branch+x[1]) /* same branch */
{++x[2];found=1;break;}
if(!found)
M[a].push_back(std::array<int,3>{i,branch, 1});
}
R=l(R,h(a,b)-branch);
}
for(auto &[_,branchinfo]:M){
int ok=1;
for(auto&x:branchinfo)if(x[2]>(N/2))ok=0;
if(ok)return R;
}
return -R;
}
}
Compilation message
towns.cpp:21:19: error: 'vector' is not a member of 'std'
21 | std::map<int,std::vector<std::array<int,3>>>M;
| ^~~~~~
towns.cpp:20:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
19 | #include<map>
+++ |+#include <vector>
20 | /* each branch store [arbitary node, branch length (to that node), count of leaves node in branch] */
towns.cpp:21:42: error: template argument 2 is invalid
21 | std::map<int,std::vector<std::array<int,3>>>M;
| ^~
towns.cpp:21:42: error: template argument 4 is invalid
towns.cpp:21:44: error: expected unqualified-id before '>' token
21 | std::map<int,std::vector<std::array<int,3>>>M;
| ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:24:5: error: 'memset' was not declared in this scope
24 | memset(cache,-1,sizeof cache);
| ^~~~~~
towns.cpp:20:1: note: 'memset' is defined in header '<cstring>'; did you forget to '#include <cstring>'?
19 | #include<map>
+++ |+#include <cstring>
20 | /* each branch store [arbitary node, branch length (to that node), count of leaves node in branch] */
towns.cpp:36:17: error: 'M' was not declared in this scope
36 | M.clear(),R=h(a,b)-branch;
| ^
towns.cpp:38:19: error: 'M' was not declared in this scope
38 | ++M[a];
| ^
towns.cpp:57:17: error: 'M' was not declared in this scope
57 | M.clear(),R=h(a,b)-branch;
| ^
towns.cpp:62:29: error: 'M' was not declared in this scope
62 | for(auto &x:M[a])
| ^
towns.cpp:66:21: error: 'M' was not declared in this scope
66 | M[a].push_back(std::array<int,3>{i,branch, 1});
| ^
towns.cpp:72:34: error: 'M' was not declared in this scope
72 | for(auto &[_,branchinfo]:M){
| ^
towns.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
80 | }
| ^
