Submission #432134

#	Time	Username	Problem	Language	Result	Execution time	Memory
432134		arayi	Towns (IOI15_towns)	C++17	38 / 100	26 ms	936 KiB

towns

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

const int N = 150;

int n;
int d[N][N];
int col[N];
bool stg(int l, int a, int b)
{
	memset(col, 0, sizeof(col));
	int sm1, sm2;
	sm1=sm2=0;
	for (int i = 0; i < n; i++)
	{
		int c = (d[a][i] + d[a][b] - d[i][b]) / 2;
		if(c < l) sm1++;
		else if(c == l) col[i] = 1;
		else sm2++;
	}
	if(sm1 > n/2 || sm2 > n/2) return 0;
	for (int i = 0; i < n; i++)
	{
		if(!col[i]) continue;
		for (int j = i + 1; j < n; j++)
		{
			if(!col[j]) continue;
			int c = (d[a][i] + d[a][j] - d[i][j]) / 2;
			if(c > l) col[i]++, col[j]++;
		}
	}
	for (int i = 0; i < n; i++) if(col[i] > n/2) return 0;
	return 1;
}
int hubDistance(int N, int sub) 
{
	n = N;
	if(sub == 3)
	{
		int a, b;
		a = b = 0;
		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++)
			{
				d[i][j] = d[j][i] = getDistance(i, j);
				if(d[i][j] > d[a][b]) a = i, b = j;
			}
		int l = 0;
		bool bl = 1;
		for (int i = 0; i < n; i++)
		{
			if(i==a||i==b) continue;
			int c = (d[a][i] + d[a][b] - d[i][b]) / 2;
			if(max(l, d[a][b] - l) > max(c, d[a][b] - c)) l = c;
			else if(max(l, d[a][b] - l) == max(c, d[a][b] - c)) l = max(l, c);
		}
		bl = stg(l, a, b);
		l = 0;
		for (int i = 0; i < n; i++)
		{
			if(i==a||i==b) continue;
			int c = (d[a][i] + d[a][b] - d[i][b]) / 2;
			if(max(l, d[a][b] - l) > max(c, d[a][b] - c)) l = c;
			else if(max(l, d[a][b] - l) == max(c, d[a][b] - c)) l = min(l, c);
		}
		if(bl || stg(l, a, b)) return max(l, d[a][b] - l);
		else return -max(l, d[a][b] - l);
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) d[i][j] = 0;
	int a = 0;
	for (int i = 1; i < n; i++)
	{
		d[0][i] = d[i][0] = getDistance(0, i);
		if(d[0][i] > d[0][a]) a = i;
	}
	int b = 0;
	for (int i = 1; i < n; i++)
	{
		if(a == i) continue;
		d[a][i] = d[i][a] = getDistance(a, i);
		if(d[a][i] > d[a][b]) b = i;
	}
	int pat = d[a][b];
	int sm = (d[a][0] + d[0][b] - d[a][b]) / 2;
	sm = d[a][0] - sm;
	int i1 = 0;
	//cout << sm << endl;
	for (int i = 0; i < n; i++)
	{
		if(i == a || i == b) continue;
		if(b == 0 || i == 0)
		{
			int c = (d[a][i]+d[i][b] - d[a][b]) / 2;
			pat = min(pat, max(d[a][i], d[i][b]) - c);
		}
		else
		{
			int l = (d[a][i1] + d[i1][i] - d[a][i]) / 2;
			l = d[a][i1] - l;
			if(sm > l) pat = min(pat, max(l, d[a][b] - l));
			else if(sm == l)
			{
				d[b][i] = d[i][b] = getDistance(b, i);
				int c = (d[a][i] + d[a][b] - d[b][i]) / 2;
				pat = min(pat, max(c, d[a][b] - c));
			}
		}
	}
	return pat;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:36:21: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   36 | int hubDistance(int N, int sub)
      |                 ~~~~^
towns.cpp:5:11: note: shadowed declaration is here
    5 | const int N = 150;
      |           ^

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