Submission #264746

#	Time	Username	Problem	Language	Result	Execution time	Memory
264746		patrikpavic2	Towns (IOI15_towns)	C++17	25 / 100	25 ms	1280 KiB

towns

/**
* user:  dlendvaj
* fname: Dorijan
* lname: Lendvaj
* task:  towns
* score: 25.0
* date:  2019-06-23 12:10:45.595704
*/
#include "towns.h"
#define x first
#define y second
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define vi vector<int>
#define vl vector<ll>
using namespace std;
const int MOD=1000000007,N=510,M=1<<19;
const char en='\n';
const ll LLINF=1ll<<60;

int d[N][N];

int dist(int a,int b)
{
	if (a>b) swap(a,b);
	if (d[a][b]!=-1) return d[a][b];
	if (a==b) return d[a][b]=0;
	return d[a][b]=getDistance(a,b);
}

int par[N],cnt[N];

int find(int i)
{
	if (par[i]==i) return i;
	return par[i]=find(par[i]);
}

void merge(int a,int b)
{
	a=find(a);
	b=find(b);
	if (a!=b) par[a]=b,cnt[b]+=cnt[a];
}

int hubDistance(int N, int sub) {
	for (int i=0;i<N;++i) for (int j=0;j<N;++j) d[i][j]=-1;
	int s=0;
	for (int i=1;i<N;++i) if (dist(0,i)>dist(0,s)) s=i;
	int t=0;
	for (int i=1;i<N;++i) if (dist(s,i)>dist(s,t)) t=i;
	int R=MOD;
	bool aa=0,bb=0,na=0,nb=0;
	int d=dist(s,t);
	for (int i=0;i<N;++i)
	{
		R=min(R,max(dist(i,s),dist(i,t))-(dist(i,s)+dist(i,t)-d)/2);
		//cout<<i<<' '<<(dist(i,s)+dist(i,t)-d)/2<<' '<<dist(i,s)<<' '<<dist(i,t)<<endl;
		if (R==max(dist(i,s),dist(i,t))-(dist(i,s)+dist(i,t)-d)/2)
		{
			if (max(dist(i,s),dist(i,t))==dist(i,s)) aa=1;
			else na=1;
			if (max(dist(i,s),dist(i,t))==dist(i,t)) bb=1;
			else nb=1;
		}
	}
	if (sub<=2) return R;
	set<int> a,b;
	vector<bool> bio;
	for (int i=0;i<N;++i) bio.pb(0);
	if (aa^na)
	{
		for (int i=0;i<N;++i)
		{
			int odd=(dist(i,s)+dist(i,t)-d)/2;
			if (aa)
			{
				if (odd+R>dist(i,s)) a.insert(i);
				if (odd+R<dist(i,s)) b.insert(i);
			}
			if (na)
			{
				if (odd+d-R>dist(i,s)) a.insert(i);
				if (odd+d-R<dist(i,s)) b.insert(i);
			}
		}
	}
	else
	{
		for (int i=0;i<N;++i)
		{
			int odd=(dist(i,s)+dist(i,t)-d)/2;
			//cout<<i<<' '<<odd<<' '<<d<<' '<<R<<endl;
			if (odd+d-R>dist(i,s)) a.insert(i);
			if (odd+R<dist(i,s)) b.insert(i);
		}
	}
	const bool Debug=0;
	for (auto x: a)
	{
		bio[x]=1;
		if (Debug) cout<<x<<" is in a"<<endl;
	}
	for (auto x: b)
	{
		bio[x]=1;
		if (Debug) cout<<x<<" is in b"<<endl;
	}
	//cout<<"s="<<s<<", t="<<t<<endl;
	if (a.size()>N/2 || b.size()>N/2) return -R;
	vi c;
	for (int i=0;i<N;++i) if (!bio[i]) c.pb(i);
	if (c.size()==1) return R;
	srand(2387);
	for (int i=0;i<c.size();++i) par[c[i]]=c[i],cnt[c[i]]=1;
	for (int i=0;i<N*N*N && c.size()>1;++i)
	{
		int x=c[rand()%c.size()];
		int y=c[rand()%c.size()];
		if (dist(x,y)*2!=dist(s,x)+dist(s,y)+dist(t,x)+dist(t,y)-2*d)
		{
			merge(x,y);
			c.erase(find(c.begin(),c.end(),x));
			if (cnt[find(y)]>N/2) return -R;
		}
	}
	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:48:31: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   48 | int hubDistance(int N, int sub) {
      |                               ^
towns.cpp:19:26: note: shadowed declaration is here
   19 | const int MOD=1000000007,N=510,M=1<<19;
      |                          ^
towns.cpp:56:6: warning: declaration of 'd' shadows a global declaration [-Wshadow]
   56 |  int d=dist(s,t);
      |      ^
towns.cpp:23:5: note: shadowed declaration is here
   23 | int d[N][N];
      |     ^
towns.cpp:112:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |  if (a.size()>N/2 || b.size()>N/2) return -R;
      |      ~~~~~~~~^~~~
towns.cpp:112:30: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |  if (a.size()>N/2 || b.size()>N/2) return -R;
      |                      ~~~~~~~~^~~~
towns.cpp:117:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for (int i=0;i<c.size();++i) par[c[i]]=c[i],cnt[c[i]]=1;
      |               ~^~~~~~~~~
towns.cpp:55:12: warning: variable 'bb' set but not used [-Wunused-but-set-variable]
   55 |  bool aa=0,bb=0,na=0,nb=0;
      |            ^~
towns.cpp:55:22: warning: variable 'nb' set but not used [-Wunused-but-set-variable]
   55 |  bool aa=0,bb=0,na=0,nb=0;
      |                      ^~

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