Submission #71622

#	Time	Username	Problem	Language	Result	Execution time	Memory
71622		Sa1378	Towns (IOI15_towns)	C++17	26 / 100	36 ms	5304 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define N ((int)230)

int dis[N],dis2[N],dis3[N];
map <int,vector <int> > mp[2];
bool mark[N];

int hubDistance(int n, int sub)
{
	mp[0].clear();mp[1].clear();
	int id=0,maxi=0;
	for(int i=1;i<n;i++)
	{
		int ex=getDistance(0,i);
		if(ex>maxi)maxi=ex,id=i;
	}
	dis[0]=maxi;dis[id]=0;
	int id2=0;
	for(int i=1;i<n;i++)
		if(i!=id)
		{
			dis[i]=getDistance(id,i);
			if(dis[i]>maxi)maxi=dis[i],id2=i;
		}
	dis2[id]=maxi;dis2[id2]=0;
	for(int i=0;i<n;i++)
		if(i!=id && i!=id2)
			dis2[i]=getDistance(id2,i);
	int R=(int)1e9;
	int cnt0=0;
	for(int i=0;i<n;i++)
	{
		bool p=(dis[i]>dis2[i]);
		if(p==0)cnt0++;
		int ex=(dis2[id]+abs(dis2[i]-dis[i]))/2;
		R=min(R,ex);
		mp[p][ex].push_back(i);
	}
	vector <int> vec;
	int x0=mp[0].begin()->first,x1=mp[1].begin()->first;
	if(x0==R && x1==R)
	{
		if(cnt0<=n/2)
		{
			vec=mp[1].begin()->second;
			if(n-cnt0-(int)vec.size()>n/2)return -R;
		}
		else
		{
			vec=mp[0].begin()->second;
			if(cnt0-(int)vec.size()>n/2)return -R;
		}
	}
	else if(x0==R)
	{
		vec=mp[0].begin()->second;
		if(n-cnt0>n/2 || cnt0-(int)vec.size()>n/2)return -R;
	}
	else
	{
		vec=mp[1].begin()->second;
		if(cnt0>n/2 || n-cnt0-(int)vec.size()>n/2)return -R;
	}
	if(vec.size()<=n/2)return R;
	memset(mark,0,sizeof mark);
	for(auto u:vec)
		dis3[u]=(dis[u]+dis2[u]-dis2[id])/2;
	for(auto u:vec)
	{
		if(mark[u])continue;
		int cnt=1;mark[u]=1;
		for(auto v:vec)
			if(!mark[v] && getDistance(u,v)!=dis3[u]+dis3[v])
				mark[v]=1,cnt++;
		if(cnt>n/2)return -R;
	}
	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:66:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(vec.size()<=n/2)return R;
     ~~~~~~~~~~^~~~~
towns.cpp:10:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub)
                            ^~~

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