This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int const NN=120;
int dis[NN][NN];
int getDistance(int i, int j);
int hubDistance(int N, int sub){
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
dis[i][j]=-int(i!=j);
int b=0;
for(int i=1;i<N;i++){
dis[0][i]=dis[i][0]=getDistance(0,i);
if(dis[0][i]>=dis[0][b])
b=i;
}
int c=0;
for(int i=1;i<N;i++)
if(i!=b){
dis[i][b]=dis[b][i]=getDistance(i,b);
if(dis[b][i]>=dis[b][c])
c=i;
}
int bc=dis[b][c];
for(int i=1;i<N;i++)
if(i!=b && i!=c)
dis[c][i]=dis[i][c]=getDistance(i,c);
int red=bc;
vector<pair<int,int>> black;
for(int i=0;i<N;i++){
int bi=dis[b][i];
int ci=dis[c][i];
int t=((bi+ci)-bc)/2;
red=min(red,max(bi-t,ci-t));
}
int u=b;
int v=c;
int com_u=0,com_v=0;
int r1=0,r2=0;
vector<int> rd1,rd2;
for(int i=0;i<N;i++){
int t=((dis[u][i]+dis[v][i]-bc)/2);
int ubl=dis[u][i]-t;
int vbl=dis[v][i]-t;
if(ubl<=vbl){
if(vbl==red){
r1++;
rd1.push_back(i);
}
else
com_u++;
}
else{
if(ubl==red){
r2++;
rd2.push_back(i);
}
else
com_v++;
}
}
int hlf=N/2;
if(sub!=3){
if(com_v>hlf || com_u>hlf || r1>hlf || r2>hlf)
red*=-1;
return red;
}
//check all
if(com_u>hlf || com_v>hlf)
return -red;
if(r1<=hlf && r2<=hlf)
return red;
for(int l1:rd1){
int com=0;
for(int l2:rd1){
if(dis[l1][l2]==-1)
dis[l1][l2]=dis[l2][l1]=getDistance(l1,l2);
int d=dis[v][l1]+dis[v][l2]-dis[l1][l2];
if(d!=red*2)
com++;
}
if(com>hlf)
return -red;
}
for(int l1:rd2){
int com=0;
for(int l2:rd2){
if(dis[l1][l2]==-1)
dis[l1][l2]=dis[l2][l1]=getDistance(l1,l2);
int d=dis[u][l1]+dis[u][l2]-dis[l1][l2];
if(d!=red*2)
com++;
}
if(com>hlf)
return -red;
}
return red;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |