Submission #640248

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

towns

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

int dis[111][111];
int hubDistance(int N, int sub) {
	int maxi=-1,maxj=-1,maxx=-1;
	int 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>X;
	for(int i=0;i<N;i++)
	{
		if(i!=maxi && i!=maxj)
		{
			dis[maxj][i]=dis[i][maxj]=getDistance(maxj,i);
			X.push_back((dis[maxi][i]-dis[maxj][i]+maxx)/2);
		}
	}
	sort(X.begin(),X.end());
	for(auto &k:X)
	{
		R=min(R,max(maxx-k,k));
	}
	int ch=-1;
	int cnt[3];
	for(int i=0;i<3;i++)cnt[i]=0;
	cnt[0]=cnt[2]=1;
	for(auto &k:X)
	{
		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:X)
	{
		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;
}

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: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39