| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 714879 | lam | Towns (IOI15_towns) | C++14 | 0 ms | 0 KiB |
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 <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "graderlib.c"
#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);
// cerr<<u<<" - "<<v<<" = "<<d[u][v]<<endl;
}
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; dist=0;
u=0;
for (int i=1; i<n; i++) if (dist<Ask(0,i))
{
u=i;
dist=Ask(0,i);
}
v=0; dist=Ask(0,u);
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,0);
int z=Ask(u,0);
up[i] = (x+y-z)/2;
ds[i] = x-up[i];
// cout<<x<<' '<<y<<' '<<z<<'\n';
// cout<<i<<" := "<<up[i]<<' '<<ds[i]<<'\n';
R=min(R,max(ds[i],dist-ds[i]));
cnt[{ds[i],dist-ds[i]}]++;
}
int sum = 0;
int it = 0;
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=0;
break;
}
else if (sum<=n/2&&(n-sz-sum)<=n/2)
{
it=i.ff.ff;
}
}
sum+=sz;
}
if (it!=0)
{
if (check(it)) dau=1;
else dau=-1;
}
return dau*R;
}
int main() {
FILE *f;
f = freopen("towns.in","r",stdin);
assert(f != NULL);
f = freopen("towns.out","w",stdout);
assert(f != NULL);
int ncase, R, N;
int subtask;
int ret;
ret = scanf("%d%d",&subtask,&ncase);
assert(ret == 2);
for (int i = 0; i < ncase; i++) {
ret = scanf("%d",&N);
assert(ret == 1);
_ini_query(N,subtask);
R=hubDistance(N,subtask);
// printf("%d\n",_user_query);
printf("%d\n",R);
}
return 0;
}