Submission #590941

#	Time	Username	Problem	Language	Result	Execution time	Memory
590941		yutabi	Towns (IOI15_towns)	C++14	13 / 100	14 ms	996 KiB

towns

#include "towns.h"


#include <bits/stdc++.h>
using namespace std;


int hubDistance(int N, int sub)
{
	if(sub==3)
	{
		int dist[200][200];
		int hub_dist[200];

		for(int i=0;i<N;i++)
		{
			for(int j=i+1;j<N;j++)
			{
				dist[i][j]=dist[j][i]=getDistance(i,j);
			}
		}

		int R=1000090007;

		int best=0;
		int d1=0;
		int d2=0;

		for(int i=1;i<N;i++)
		{
			if(dist[0][i]>best)
			{
				best=dist[0][i];

				d1=i;
			}
		}

		for(int i=0;i<N;i++)
		{
			if(i!=d1)
			{
				if(dist[d1][i]>best)
				{
					best=dist[d1][i];

					d2=i;
				}
			}
		}

		bool dbl=0;

		for(int i=0;i<N;i++)
		{
			if(i!=d1 && i!=d2)
			{
				int sum=(dist[d1][i]+dist[d2][i]-dist[d1][d2])/2;

				if(R==max(dist[d1][i]-sum,dist[d2][i]-sum))
				{
					dbl=1;
				}

				if(R>max(dist[d1][i]-sum,dist[d2][i]-sum))
				{
					R=max(dist[d1][i]-sum,dist[d2][i]-sum);

					hub_dist[d1]=dist[d1][i]-sum;
					hub_dist[d2]=dist[d2][i]-sum;

					dbl=0;
				}
			}
		}


		if(dbl)
		{
			int d1_count=0;
			int d2_count=0;

			for(int i=0;i<N;i++)
			{
				if(i!=d1 && i!=d2)
				{
					int sum=(dist[d1][i]+dist[d2][i]-dist[d2][d1])/2;

					if(dist[d1][i]-sum<R)
					{
						d2_count++;
					}

					else
					{
						d1_count++;
					}
				}
			}

			if(d1_count>=d2_count)
			{
				hub_dist[d1]=R;
				hub_dist[d2]=dist[d1][d2]-R;
			}

			else
			{
				hub_dist[d2]=R;
				hub_dist[d1]=dist[d1][d2]-R;
			}
		}

		for(int i=0;i<N;i++)
		{
			if(i!=d1 && i!=d2)
			{
				int sum=(dist[d1][i]+dist[d2][i]-dist[d2][d1])/2;

				hub_dist[i]=abs(dist[d1][i]-sum-hub_dist[d1])+sum;
			}
		}

		bool flag=0;

		for(int i=0;i<N;i++)
		{
			int c=1;

			for(int j=i+1;j<N;j++)
			{
				if(dist[i][j]<hub_dist[i]+hub_dist[j])
				{
					c++;
				}
			}

			if(c*2>N)
			{
				flag=1;

				break;
			}
		}

		if(flag)
		{
			return -R;
		}

		return R;
	}


	int R=1000090007;

	int best=0;
	int d1=0;
	int d2=0;


	int d1_dist[200];
	int d2_dist[200];
	int hub_dist[200];


	for(int i=1;i<N;i++)
	{
		int res=getDistance(0,i);

		if(res>best)
		{
			best=res;

			d1=i;
		}
	}

	d1_dist[0]=best;

	for(int i=1;i<N;i++)
	{
		if(i!=d1)
		{
			int res=getDistance(d1,i);

			if(res>best)
			{
				best=res;

				d2=i;
			}

			d1_dist[i]=res;
		}
	}

	d2_dist[d1]=best;

	for(int i=0;i<N;i++)
	{
		if(i!=d1 && i!=d2)
		{
			d2_dist[i]=getDistance(d2,i);
		}
	}

	bool dbl=0;

	for(int i=0;i<N;i++)
	{
		if(i!=d1 && i!=d2)
		{
			int sum=(d1_dist[i]+d2_dist[i]-d1_dist[d2])/2;

			if(R==max(d1_dist[i]-sum,d2_dist[i]-sum))
			{
				dbl=1;
			}

			if(R>max(d1_dist[i]-sum,d2_dist[i]-sum))
			{
				R=max(d1_dist[i]-sum,d2_dist[i]-sum);

				hub_dist[d1]=d1_dist[i]-sum;
				hub_dist[d2]=d2_dist[i]-sum;

				dbl=0;
			}
		}
	}


	if(dbl)
	{
		int d1_count=0;
		int d2_count=0;

		for(int i=0;i<N;i++)
		{
			if(i!=d1 && i!=d2)
			{
				int sum=(d1_dist[i]+d2_dist[i]-d2_dist[d1])/2;

				if(d1_dist[i]-sum<R)
				{
					d2_count++;
				}

				else
				{
					d1_count++;
				}
			}
		}

		if(d1_count>=d2_count)
		{
			hub_dist[d1]=R;
			hub_dist[d2]=d1_dist[d2]-R;
		}

		else
		{
			hub_dist[d2]=R;
			hub_dist[d1]=d1_dist[d2]-R;
		}
	}

	int grp_d1=1;
	int grp_d2=1;
	int grp_oth=0;

	for(int i=0;i<N;i++)
	{
		if(i!=d1 && i!=d2)
		{
			int sum=(d1_dist[i]+d2_dist[i]-d1_dist[d2])/2;

			if(d1_dist[i]-sum<hub_dist[d1])
			{
				grp_d1++;
			}

			else if(d1_dist[i]-sum>hub_dist[d1])
			{
				grp_d2++;
			}

			else
			{
				grp_oth++;
			}
		}
	}

	printf("%d %d\n",d1,d2);

	for(int i=0;i<N;i++)
	{
		printf("%d ",d1_dist[i]);
	}

	printf("\n");

	for(int i=0;i<N;i++)
	{
		printf("%d ",d2_dist[i]);
	}

	printf("\n");

	for(int i=0;i<N;i++)
	{
		printf("%d ",hub_dist[i]);
	}

	printf("\n");

	if(grp_d1*2>N || grp_d2*2>N || grp_oth*2>N)
	{
		return -R;
	}

	return R;
}

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