Submission #590923

#	Time	Username	Problem	Language	Result	Execution time	Memory
590923		yutabi	Towns (IOI15_towns)	C++14	25 / 100	21 ms	980 KiB

towns

#include "towns.h"


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


int hubDistance(int N, int sub)
{
	int R=1000000007;

	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);
		}
	}

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

			R=min(R,max(d1_dist[i]-sum,d2_dist[i]-sum));
		}
	}

	int d1_count=0,d2_count=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==d1_dist[i]-sum)
			{
				d1_count++;
			}
			
			else if(R==d2_dist[i]-sum)
			{
				d2_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++;
			}

			if(d1_dist[i]-sum==hub_dist[d1])
			{
				grp_oth++;
			}

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

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

	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:8:28: warning: unused parameter 'sub' [-Wunused-parameter]
    8 | int hubDistance(int N, int sub)
      |                        ~~~~^~~

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