Submission #640304

#	Time	Username	Problem	Language	Result	Execution time	Memory
640304		ggoh	Towns (IOI15_towns)	C++14	22 / 100	14 ms	468 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int>pii;

int dis[111][111];
int ch,n,maxi,maxj,maxx;
struct tri{
	int a,b,c;
};
bool cmp(tri A, tri B){return A.a<B.a;}
vector<tri>X;
void f(int r)
{
	if(ch==1)return ;
	int cnt0=1,cnt1=1,cnt2=0;
	for(auto &k:X)
	{
		if(k.a==r)cnt2++;
		else if(k.a<r)cnt0++;
		else cnt1++;
	}
	if(cnt0>n/2 || cnt1>n/2)return  ;
	if(cnt2<=n/2)
	{
		ch=1;
		return ;
	}
	vector<pii>C;
	for(auto &k:X)
	{
		 if(k.a==r)C.push_back({k.b,k.c});
		 else if(k.a<r)C.push_back({r-k.a+k.b,k.c});
		 else C.push_back({k.a-r+k.b,k.c});
	}
	C.push_back({r,maxi});
	C.push_back({maxx-r,maxj});
	int siz=1;
	vector<int>V[113],D[113];
	vector<int>H(n);
	for(auto &k:C)H[k.second]=k.first;
	for(int i=0;i<n;i++)
	{
		if(V[siz].empty())V[siz].push_back(i);
		else
		{
			if(!dis[V[siz][0]][i])dis[V[siz][0]][i]=dis[i][V[siz][0]]=getDistance(V[siz][0],i);
			if(dis[V[siz][0]][i]==H[V[siz][0]]+H[i])D[siz].push_back(i);
			else V[siz].push_back(i);
			if(sz(V[siz])==sz(D[siz]))
			{
				siz++;
			}
		}
	}
	int o=0;
	int candi=V[siz][0];
	o+=sz(V[siz]);
	for(int j=1;j<siz;j++)
	{
		if(!dis[V[j][0]][candi])dis[V[j][0]][candi]=dis[candi][V[j][0]]=getDistance(V[j][0],candi);
		if(dis[V[j][0]][candi]==H[V[j][0]]+H[candi])
		{
			for(auto &k:D[j])
			{
				if(!dis[k][candi])dis[k][candi]=dis[candi][k]=getDistance(k,candi);
				if(dis[k][candi]!=H[k]+H[candi])o++;
			}
		}
		else
		{
			o+=sz(V[j]);
		}
	}
	if(o<=n/2)ch=1;
}
int hubDistance(int N, int sub) {
	int R=1e9;
	if(sub!=2 && sub!=4){
	maxi=-1,maxj=-1,maxx=-1;
	n=N;
	memset(dis,0,sizeof(dis));
	for(int i=1;i<N;i++)
	{
		dis[0][i]=dis[i][0]=getDistance(0,i);
		if(dis[0][i]>maxx)
		{
			maxx=dis[0][i];
			maxi=i;
		}
	}
	maxx=-1;
	for(int i=0;i<N;i++)
	{
		if(i!=maxi)
		{
			if(!dis[maxi][i])dis[maxi][i]=dis[i][maxi]=getDistance(i,maxi);
			if(dis[maxi][i]>maxx)
			{
				maxx=dis[maxi][i];
				maxj=i;
			}
		}
	}
	X.clear();
	for(int i=0;i<N;i++)
	{
		if(i!=maxi && i!=maxj)
		{
			if(!dis[maxj][i])dis[maxj][i]=dis[i][maxj]=getDistance(maxj,i);
			X.push_back({(dis[maxi][i]-dis[maxj][i]+maxx)/2,(dis[maxi][i]+dis[maxj][i]-maxx)/2,i});
		}
	}
	sort(X.begin(),X.end(),cmp);
	for(auto &k:X)
	{
		R=min(R,max(maxx-k.a,k.a));
	}
	ch=-1;
	f(R);
	if(R!=maxx-R)f(maxx-R);

	return ch*R;
	}

	else
	{
		maxi=-1,maxj=-1,maxx=-1;
		R=1e9;
	for(int i=1;i<N;i++)
	{
		dis[0][i]=dis[i][0]=getDistance(0,i);
		if(dis[0][i]>maxx)
		{
			maxx=dis[0][i];
			maxi=i;
		}
	}
	maxx=-1;
	for(int i=0;i<N;i++)
	{
		if(i!=maxi)
		{
			dis[maxi][i]=dis[i][maxi]=getDistance(maxi,i);
			if(dis[maxi][i]>maxx)
			{
				maxx=dis[maxi][i];
				maxj=i;
			}
		}
	}
	vector<int>Z;
	for(int i=0;i<N;i++)
	{
		if(i!=maxi && i!=maxj)
		{
			dis[maxj][i]=dis[i][maxj]=getDistance(maxj,i);
			Z.push_back((dis[maxi][i]-dis[maxj][i]+maxx)/2);
		}
	}
	sort(Z.begin(),Z.end());
	for(auto &k:Z)
	{
		R=min(R,max(maxx-k,k));
	}
	ch=-1;
	int cnt[3];
	for(int i=0;i<3;i++)cnt[i]=0;
	cnt[0]=cnt[2]=1;
	for(auto &k:Z)
	{
		if(k<R)cnt[0]++;
		else if(k==R)cnt[1]++;
		else cnt[2]++;
	}
	if(cnt[0]<=N/2 && cnt[1]<=N/2 && cnt[2]<=N/2)ch=1;
	for(int i=0;i<3;i++)cnt[i]=0;
	cnt[0]=cnt[2]=1;
	for(auto &k:Z)
	{
		if(k<maxx-R)cnt[0]++;
		else if(k==maxx-R)cnt[1]++;
		else cnt[2]++;
	}
	if(cnt[0]<=N/2 && cnt[1]<=N/2 && cnt[2]<=N/2)ch=1;
 
 
	return ch*R;
	}
}

• Subtask 1: 0 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39