Submission #1157427

#TimeUsernameProblemLanguageResultExecution timeMemory
1157427Doncho_BonbonchoTowns (IOI15_towns)C++20
13 / 100
10 ms328 KiB
#include "towns.h" #include <bits/stdc++.h> #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 ); 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...