Submission #1157434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157434		Doncho_Bonboncho	Towns (IOI15_towns)	C++20	25 / 100	10 ms	328 KiB

towns

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

#ifndef LOCAL
#define cerr if(false) cerr
#endif


template< class T, class T2 > inline bool chkmax( T& a, const T2& b ){ return a < b ? a = b, 1 : 0 ; };
template< class T, class T2 > inline bool chkmin( T& a, const T2& b ){ return a > b ? a = b, 1 : 0 ; };

#define out(x) #x << " = " << x << "  "

typedef long long ll;

const int MAX_N = 128;
const ll inf = 1e18;

int n;

std::map<std::pair< int, int >, ll > q;
ll makeQuery( int a, int b ){
	//return getDistance( a, b );

	if( a > b ) std::swap( a, b );
	if( a == b ) return 0;
	std::pair< int, int > curr = { a, b };
	if( q.find( curr ) == q.end() ) q[curr] = getDistance( a, b );
	return q[curr];
}

int hubDistance(int N, int sub) {
	q.clear();
	n = N;

	ll mxDist = -1;

	int d1, d2;
	for( int i=0 ; i < n ; i++ ){
		if( i == 0 ) continue;
		ll currDist = makeQuery( 0, i );
		if( chkmax( mxDist, currDist ) ) d1 = i;
	}

	mxDist = -1;
	for( int i=0 ; i < n ; i++ ){
		if( i == d1 ) continue;
		ll currDist = makeQuery( d1, i );
		if( chkmax( mxDist, currDist ) ) d2 = i;
	}
	ll distDiam = getDistance( d1, d2 );
	//cerr << out( d1 ) << out( d2 ) << out( getDistance( d1, d2 ) ) << endl;

	ll nas = inf;
	for( int i=0 ; i < n ; i++ ){
		if( i == d1 || i == d2 ) continue;
		ll A = makeQuery( i, d1 );
		ll B = distDiam;
		ll C = makeQuery( d2, i );
		//cerr << out( i ) << out( A ) << out( B ) << out( C ) << endl;
		ll dist = ( A + B - C ) / 2LL;
		ll currNas = std::max( dist, distDiam - dist );
		chkmin( nas, currNas );
	}

	cerr << out( nas ) << endl;
	return -nas;
}

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