Submission #113287

#	Time	Username	Problem	Language	Result	Execution time	Memory
113287		TadijaSebez	Towns (IOI15_towns)	C++11	48 / 100	20 ms	512 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=120;
int n,cen,den;
int a[N],b[N],c[N],len[N];
int d[N][N],diam;
bool was[N][N];
int Ask(int i, int j)
{
	if(i==j) return 0;
	if(!was[i][j]) d[i][j]=d[j][i]=getDistance(i,j);
	was[i][j]=was[j][i]=1;
	return d[i][j];
}
bool Try(int d)
{
	vector<int> work;
	int lo=1,hi=1;
	for(int i=0;i<n;i++) if(i!=cen && i!=den)
	{
		int tmp=(c[i]+diam-b[i])/2;
		if(tmp<d) lo++;
		if(tmp>d) hi++;
		if(tmp==d) work.pb(i);
	}
	if(lo>n/2 || hi>n/2) return 0;
	while(work.size()>n/2)
	{
		random_shuffle(work.begin(),work.end());
		int sz=1,u=work.back();
		work.pop_back();
		vector<int> tmp;
		for(int v:work)
		{
			if(Ask(u,v)==len[u]+len[v]) tmp.pb(v);
			else sz++;
		}
		if(sz>n/2) return 0;
		work=tmp;
	}
	return 1;
}
int hubDistance(int _N, int sub)
{
	srand(time(0));
	n=_N;cen=den=0;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) was[i][j]=0;
	for(int i=0;i<n;i++) a[i]=b[i]=c[i]=0;
	for(int i=1;i<n;i++)
	{
		a[i]=Ask(0,i);
		if(a[i]>a[cen]) cen=i;
	}
	for(int i=0;i<n;i++) if(i!=cen)
	{
		b[i]=Ask(cen,i);
		if(b[i]>b[den]) den=i;
	}
	diam=b[den];
	int 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]=Ask(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++;
		len[i]=(c[i]+b[i]-diam)/2;
	}
	if(sub==3 || sub==5 || sub==6)
	{
		bool ok=0;
		if(Try(ans) || Try(diam-ans)) ok=1;
		ans=max(ans,diam-ans);
		if(ok) return ans;
		else return -ans;
	}
	vector<int> work;
	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++;
		if(tmp==ans) work.pb(i);
	}
	ans=max(ans,diam-ans);
	if(sub<3) return ans;
	if(sub==4)
	{
		if(lo>n/2 || hi>n/2 || cnt>n/2) return -ans;
		return ans;
	}
	return ans;
}

Compilation message (stderr)

towns.cpp: In function 'bool Try(int)':
towns.cpp:17:15: warning: declaration of 'd' shadows a global declaration [-Wshadow]
 bool Try(int d)
               ^
towns.cpp:8:5: note: shadowed declaration is here
 int d[N][N],diam;
     ^
towns.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(work.size()>n/2)
        ~~~~~~~~~~~^~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:47:12: warning: conversion to 'unsigned int' from 'time_t {aka long int}' may alter its value [-Wconversion]
  srand(time(0));
        ~~~~^~~

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