| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1096759 | MMihalev | Towns (IOI15_towns) | C++17 | 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<iostream>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int MAX_N=2e2+2;
int diam;
int tov[MAX_N];
int tou[MAX_N];
int to0[MAX_N];
int ma[MAX_N][MAX_N];
int q;
set<int>nodes,nodes1,nodes2;
int n;
int u,v;
bool check(int a,int b)
{
int dd;
if(a>b)swap(a,b);
if(a==0)dd=to0[b];
else
{
//if(q==(n*(n-1))/2)while(1);
if(ma[a][b])
{
//if(a==u)while(1);
//if(b==u)while(1);
}
ma[a][b]=1;
dd=getDistance(a,b);
q++;
}
if(tou[a]+tov[b]-diam==dd)return 0;
return 1;
}
int hubDistance(int N, int sub)
{
nodes1.erase();
nodes2.erase();
n=N;
for(int i=0;i<n;i++)
{
to0[i]=0;
tou[i]=0;
tov[i]=0;
}
u=0;
int far=0;
for(int i=1;i<n;i++)
{
int cur=getDistance(u,i);
q++;
to0[i]=cur;
if(cur>far)
{
far=cur;
v=i;
}
}//0->v
diam=0;
for(int i=0;i<n;i++)
{
if(i==v)continue;
int cur;
if(i==0)cur=to0[v];
else {cur=getDistance(i,v);q++;}
tov[i]=cur;
if(cur>diam)
{
diam=cur;
u=i;
}
}//v->u
for(int i=0;i<n;i++)
{
if(i==u)continue;
if(i==0){tou[i]=to0[u];continue;}
if(i==v){tou[i]=tov[u];continue;}
if(u!=0){tou[i]=getDistance(u,i);q++;}
else tou[i]=to0[i];
}//u->all
int cntneg=1,cntpos=1,cntbaseneg=0,cntbasepos=0;
int mindif=1e9;
for(int i=0;i<n;i++)
{
if(i==u or i==v)continue;
int x=tou[i];
int y=tov[i];
int com=((x+y)-diam)/2;
x-=com;
y-=com;
int res=x-y;
mindif=min(mindif,abs(res));
}
for(int i=0;i<n;i++)
{
if(i==u or i==v)continue;
int x=tou[i];
int y=tov[i];
int com=((x+y)-diam)/2;
x-=com;
y-=com;
int res=x-y;
if(abs(res)==mindif)
{
if(res<=0){cntbaseneg++;nodes1.insert(i);}
else {cntbasepos++;nodes2.insert(i);}
}
else if(res<0)cntneg++;
else cntpos++;
}
int R=(diam-mindif)/2+mindif;
if(sub==4 or sub<=2)
{
if(cntbaseneg*cntbasepos!=0)
{
if(cntneg*2>n or (cntbasepos+cntpos)*2>n or cntbaseneg*2>n)return -R;
if(cntpos*2>n or (cntbaseneg+cntneg)*2>n or cntbasepos*2>n)return -R;
return R;
}
else
{
if(cntneg*2>n or cntpos*2>n or (cntbaseneg+cntbasepos)*2>n)return -R;
return R;
}
}
if(cntneg*2>n or cntpos*2>n)return -R;
if(cntbasepos*2<=n && cntbaseneg*2<=n)return R;
if(cntbaseneg*2>n)nodes=nodes1;
else nodes=nodes2;
for(int x:nodes)
{
if(x==u)while(1);
}
while(nodes.size())
{
int cnt=1;
int X=(*(nodes.begin()));
nodes.erase(X);
if(nodes.size()==0)break;
auto it=nodes.begin();
set<int>dele;
while(it!=nodes.end())
{
if(check(X,(*it)))
{
dele.insert((*it));
cnt++;
}
it++;
}
while(dele.size())
{
int el=(*(dele.begin()));
dele.erase(el);
nodes.erase(el);
}
if(2*cnt>n)return -R;
}
return R;
}