Submission #113284

#	Time	Username	Problem	Language	Result	Execution time	Memory
113284		TadijaSebez	Towns (IOI15_towns)	C++11	35 / 100	18 ms	384 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
const int N=120;
int n,cen,den;
int a[N],b[N],c[N];
int hubDistance(int _N, int sub)
{
	n=_N;cen=den=0;
	for(int i=0;i<n;i++) a[i]=b[i]=c[i]=0;
	for(int i=1;i<n;i++)
	{
		a[i]=getDistance(0,i);
		if(a[i]>a[cen]) cen=i;
	}
	for(int i=0;i<n;i++) if(i!=cen)
	{
		b[i]=getDistance(cen,i);
		if(b[i]>b[den]) den=i;
	}
	int diam=b[den],ans=diam,cnt=0,lo=1,hi=1,goal=diam/2;
	for(int i=0;i<n;i++) if(i!=cen && i!=den)
	{
		c[i]=getDistance(den,i);
		int tmp=(c[i]+diam-b[i])/2;
		//tmp=max(tmp,diam-tmp);
		if(abs(ans-goal)>abs(tmp-goal)) ans=tmp,cnt=0;
		if(ans==tmp) cnt++;
	}
	for(int i=0;i<n;i++) if(i!=cen && i!=den)
	{
		int tmp=(c[i]+diam-b[i])/2;
		if(tmp<ans) lo++;
		if(tmp>ans) hi++;
	}
	ans=max(ans,diam-ans);
	if(lo>n/2 || hi>n/2 || cnt>n/2) return -ans;
	return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:7:29: warning: unused parameter 'sub' [-Wunused-parameter]
 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