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 "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
#define ff first
#define ss second
const int maxn = 510;
int n;
int d[maxn][maxn];
int ds[maxn],up[maxn];
map<ii,int> cnt;
int Ask(int u, int v)
{
if (u==v) return 0;
if (u>v) swap(u,v);
if (d[u][v] == -1)
{
d[u][v] = getDistance(u,v);
}
return d[u][v];
}
bool check(int dist)
{
vector<int> to_mid(n+1,0);
for (int i=0; i<n; i++)
if (ds[i]<dist) to_mid[i]=dist-ds[i]+up[i];
else to_mid[i]=ds[i]-dist+up[i];
vector <int> sz(n+1,0);
int alive = 0; int num=1;
for (int i=1; i<n; i++)
if (num==0)
{
num=1;
sz[i]++; alive=i;
}
else
{
if (Ask(i,alive)==to_mid[i]+to_mid[alive])
{
num--; sz[i]++;
}
else
{
num++;
sz[alive]++;
}
}
if (num<=0) return 1;
num=0;
for (int i=0; i<n; i++) if (sz[i]!=0)
{
if (Ask(i,alive)==to_mid[i]+to_mid[alive]) num-=sz[i];
else num+=sz[i];
}
return num<=0;
}
int hubDistance(int N, int sub) {
n=N;
cnt.clear();
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) d[i][j] = -1;
int u,v,dist;
u=0;
for (int i=1; i<n; i++) if (dist<Ask(0,i))
{
u=i;
dist=Ask(0,i);
}
v=0; dist=0;
for (int i=1; i<n; i++) if (dist<Ask(u,i))
{
dist=Ask(u,i);
v=i;
}
int R=1e9;
for (int i=0; i<n; i++)
{
int x=Ask(u,i); int y=Ask(i,v);
int z=Ask(u,v);
up[i] = (x+y-z)/2;
ds[i] = Ask(u,i)-up[i];
R=min(R,max(ds[i],Ask(u,v)-ds[i]));
cnt[{ds[i],Ask(u,v)-ds[i]}]++;
}
int sum = 0;
int it = -1;
int dau = 1;
for (auto i:cnt)
{
int sz = i.ss;
if (max(i.ff.ff,i.ff.ss)==R)
{
if (sz<=n/2&&sum<=n/2&&(n-sz-sum<=n/2))
{
dau=1;
it=-1;
break;
}
else if (sum<=n/2&&(n-sz-sum)<=n/2)
{
it=i.ff.ff;
}
}
sum+=sz;
}
if (it!=-1)
{
if (check(it)) dau=1;
else dau=-1;
}
// cerr<<R<<endl;
return dau*R;
}
Compilation message (stderr)
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:59:28: warning: unused parameter 'sub' [-Wunused-parameter]
59 | int hubDistance(int N, int sub) {
| ~~~~^~~
towns.cpp:66:29: warning: 'dist' may be used uninitialized in this function [-Wmaybe-uninitialized]
66 | for (int i=1; i<n; i++) if (dist<Ask(0,i))
| ^~
# | 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... |