Submission #1057228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057228		UmairAhmadMirza	Towns (IOI15_towns)	C++17	35 / 100	9 ms	860 KiB

towns

#include <bits/stdc++.h>
using namespace std;

int const NN=120;
int dis[NN][NN];

int getDistance(int i, int j);
int hubDistance(int N, int sub){
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			dis[i][j]=-int(i!=j);
	int b=0;
	for(int i=1;i<N;i++){
		dis[0][i]=dis[i][0]=getDistance(0,i);
		if(dis[0][i]>=dis[0][b])
			b=i;
	}
	int c=0;
	for(int i=1;i<N;i++)
		if(i!=b){
			dis[i][b]=dis[b][i]=getDistance(i,b);
			if(dis[b][i]>=dis[b][c])
				c=i;
		}
	int bc=dis[b][c];
	for(int i=1;i<N;i++)
		if(i!=b && i!=c)
			dis[c][i]=dis[i][c]=getDistance(i,c);
	int red=bc;
	vector<pair<int,int>> black;
	for(int i=0;i<N;i++){
		int bi=dis[b][i];
		int ci=dis[c][i];
		int t=((bi+ci)-bc)/2;
		black.push_back({bi-t,ci-t});
		red=min(red,max(bi-t,ci-t));
	}
	int u=b;
	int v=c;
	sort(black.begin(), black.end());
	set<int> leaf;
	int com_u=0,com_v=0;
	int r1=0,r2=0;
	vector<int> rd1,rd2;
	for(int i=0;i<N;i++){
		int t=((dis[u][i]+dis[v][i]-bc)/2);
		int ubl=dis[u][i]-t;
		int vbl=dis[v][i]-t;
		if(ubl<=vbl){
			if(vbl==red){
				r1++;
				rd1.push_back(i);
			}
			else
				com_u++;
		}
		else{
			if(ubl==red){
				r2++;
				rd2.push_back(i);
			}
			else
				com_v++;
		}
	}
	int hlf=N/2;
	if(sub!=3){
		if(com_v>hlf || com_u>hlf || r1>hlf || r2>hlf)
			red*=-1;
		return red;
	}
	//check all
	for(int l1:rd1){
		int com=0;
		for(int l2:rd1){
			if(dis[l1][l2]==-1)
				dis[l1][l2]=dis[l2][l1]=getDistance(l1,l2);
			int d=dis[v][l1]+dis[v][l2]-dis[l1][l2];
			if(d>red*2)
				com++;
		}
		if(com>hlf)
			return -red;
	}
	for(int l1:rd2){
		int com=0;
		for(int l2:rd2){
			if(dis[l1][l2]==-1)
				dis[l1][l2]=dis[l2][l1]=getDistance(l1,l2);
			int d=dis[u][l1]+dis[u][l2]-dis[l1][l2];
			if(d>red*2)
				com++;
		}
		if(com>hlf)
			return -red;
	}
	if(com_u>hlf||com_v>hlf)
		return -red;
	return red;
}

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