Submission #574129

#	Time	Username	Problem	Language	Result	Execution time	Memory
574129		Lawliet	Towns (IOI15_towns)	C++17	25 / 100	16 ms	892 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 110;

int n;

int dist[maxn][maxn];

int query(int u, int v)
{
	if( u == v || dist[u][v] != 0 )
		return dist[u][v];

	return dist[u][v] = dist[v][u] = getDistance(u, v);
}

int distPath(int a, int b, int c)
{
	return (query(a, c) + query(b, c) - query(a, b))/2;
}

tuple<int,int> findDiameter()
{
	int A = 0;

	for(int i = 0 ; i < n ; i++)
		if( query( 0 , A ) < query( 0 , i ) ) A = i;

	int B = A;

	for(int i = 0 ; i < n ; i++)
		if( query( A , B ) < query( A , i ) ) B = i;

	return { A , B };
}

tuple<int,int,int> getInfoCenter(int A, int B)
{
	vector<int> leaves;
	int R = query(A, B);

	for(int i = 0 ; i < n ; i++)
	{
		int curR = distPath( 0 , i , A );
		curR = max( curR , query(A, B) - curR );

		if( curR < R )
			leaves.clear();

		if( curR <= R )
			R = curR, leaves.push_back( i );
	}

	leaves.resize( 2 , -1 );
	return { leaves[0] , leaves[1] , R };
}

int hubDistance(int N, int sub) 
{
	memset( dist , 0 , sizeof(dist) );
	
	n = N;

	auto [A, B] = findDiameter();
	auto [C1, C2, R] = getInfoCenter(A, B);

	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:61:28: warning: unused parameter 'sub' [-Wunused-parameter]
   61 | int hubDistance(int N, int sub)
      |                        ~~~~^~~

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