# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
330663 | IloveN | 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<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=1e3+10;
namespace myrand
{
mt19937 mt(chrono::system_clock::now().time_since_epoch() / chrono::microseconds(1));
ll Int(ll l,ll r) { return uniform_int_distribution<ll> (l,r)(mt);}
}
using namespace myrand;
/*int getDistance(int x,int y)
{
return 0;
}*/
int dis_t[N];
int hubDistance(int n, int sub) {
int lim;
if (sub==1 || sub==3) lim=n*(n-1)/2;
else if (sub==5) lim=5*n;
else lim=(7*n+1)/2;
int s=Int(1,n),t=0,mx=0;
for (int i=1;i<=n;i++)
if (s!=i)
{
int d=getDistance(s,i);
if (d>mx) mx=d,t=i;
}
for (int i=1;i<=n;i++)
if (i!=t)
{
int d=getDistance(t,i);
dis_t[i]=d;
if (d>mx) mx=d,s=i;
}
int res=mx;
for (int i=1;i<=n;i++)
if (i!=s && i!=t)
{
int d=getDistance(s,i);
int tmp=(d+dis_t[i]-dis_t[s])/2;
res=min(res,max(d-tmp,dis_t[i]-tmp));
}
return res;
}
/*int main()
{
//freopen("ss.inp","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}*/