Submission #590917

#	Time	Username	Problem	Language	Result	Execution time	Memory
590917		yutabi	Towns (IOI15_towns)	C++14	25 / 100	22 ms	468 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];


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

	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