結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-08-21 18:52:24 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 12,603 bytes |
| コンパイル時間 | 860 ms |
| 実行使用メモリ | 10,372 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2022-08-21 18:52:30 |
| 合計ジャッジ時間 | 5,970 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 1 -- * 29 |
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:16:78: 警告: ‘num_start’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
16 | #define FOR_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
| ^
main.cpp:335:6: 備考: ‘num_start’ はここで定義されています
335 | ll num_start;
| ^~~~~~~~~
main.cpp:93:22: 警告: ‘m_kj_min’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
93 | near_kk[1] = m_kj_min; \
| ^
main.cpp:78:12: 備考: ‘m_kj_min’ はここで定義されています
78 | ll m_kj_min; \
| ^~~~~~~~
main.cpp:206:5: 備考: in expansion of macro ‘SetNear’
206 | SetNear;
| ^~~~~~~
main.cpp:92:22: 警告: ‘m_ki_min’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
92 | near_kk[0] = m_ki_min; \
| ^
main.cpp:77:12: 備考: ‘m_ki_min’ はここで定義されています
77 | ll m_ki_min; \
| ^~~~~~~~
main.cpp:206:5: 備考: in expansion of macro ‘SetNear’
206 | SetNear;
| ^~~~~~~
main.cpp:30:30: 警告: ‘y_min’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
30 | ll p_num = ( x / W ) + ( y / H ) * Px; \
| ^
main.cpp:177:8: 備考: ‘y_min’ はここで定義されています
177 | ll y_min;
| ^~~~~
main.cpp:30:18: 警告: ‘x_min’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
30 | ll p_num = ( x / W )
ソースコード
#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <stdio.h>
#include <stdint.h>
#include <iomanip>
using namespace std;
using uint = unsigned int;
using ll = long long;
#define CIN( LL , A ) LL A; cin >> A
#define GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#define FOR_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR_LL( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define RETURN( ANSWER ) cout << ( ANSWER ) << endl; return 0
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << endl; return 0
#define MIN( A , B ) A < B ? A : B;
#define MAX( A , B ) A < B ? B : A;
template <typename T> inline T Distance( const T& a , const T& b ){ return a < b ? b - a : a - b; }
#define SetAB( x , y ) \
\
a[num] = x; \
b[num] = y; \
ll p_num = ( x / W ) + ( y / H ) * Px; \
p[num] = p_num; \
ll& m_size_p_num = m_size[p_num]; \
m[p_num][m_size_p_num] = num; \
m_size_p_num++; \
\
#define SetNear \
\
FOR_LL( k , 0 , P ){ \
ll (&m_k)[NM] = m[k]; \
ll& m_size_k = m_size[k]; \
ll (&near_k)[P][2] = near[k]; \
ll (&E_min_k)[P] = E_min[k]; \
FOR_LL( h , 0 , k ){ \
ll (&m_h)[NM] = m[h]; \
ll& m_size_h = m_size[h]; \
ll (&near_kh)[2] = near_k[h]; \
ll& E_min_kh = E_min_k[h]; \
E_min_kh = 50000025; \
FOR_LL( i , 0 , m_size_k ){ \
ll& m_ki = m_k[i]; \
ll (&Ei)[NM] = E[m_ki]; \
FOR_LL( j , 0 , m_size_h ){ \
ll& m_hj = m_h[j]; \
ll& Eij = Ei[m_hj]; \
if( Eij < E_min_kh ){ \
ll& E_min_hk = E_min[h][k]; \
E_min_kh = E_min_hk = Eij; \
ll ( &near_hk )[2] = near[h][k]; \
near_kh[0] = near_hk[1] = m_ki; \
near_kh[1] = near_hk[0] = m_hj; \
} \
} \
} \
} \
ll (&near_kk)[2] = near_k[k]; \
if( m_size_k == 1 ){ \
near_kk[0] = near_kk[1] = m_k[0]; \
} else if( m_size_k > 1 ){ \
ll E_min_max_kk = -1; \
FOR_LL( i , 0 , m_size_k ){ \
ll& m_ki = m_k[i]; \
ll (&Ei)[NM] = E[m_ki]; \
ll E_min_kk = 50000025; \
ll m_ki_min; \
ll m_kj_min; \
FOR_LL( j , 0 , m_size_k ){ \
if( j != i ){ \
ll& m_kj = m_k[j]; \
ll& Eij = Ei[m_kj]; \
if( Eij < E_min_kk ){ \
E_min_kk = Eij; \
m_ki_min = m_ki; \
m_kj_min = m_kj; \
} \
} \
} \
if( E_min_kk > E_min_max_kk ){ \
E_min_max_kk = E_min_kk; \
near_kk[0] = m_ki_min; \
near_kk[1] = m_kj_min; \
} \
} \
} \
} \
\
template <ll NM , ll P>
const ll& HeldKarp( const ll& k_start , const ll& k_goal , const ll& s , const ll (&k_valid)[P] , const ll& P_valid , const ll (&path_E)[NM][NM] , const ll (&near)[P][P][2] , const ll (&E_min)[P][P] , ll (&k_mid)[P] );
#define S 1 - 1
// #define S 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 - 1
int main()
{
// constexpr const ll N = 2;
// constexpr const ll M = 1;
// constexpr const ll Px = 1;
// constexpr const ll Py = 1;
// constexpr const ll N = 3;
// constexpr const ll M = 4;
// constexpr const ll Px = 1;
// constexpr const ll Py = 1;
constexpr const ll N = 100;
constexpr const ll M = 8;
constexpr const ll Px = 4;
constexpr const ll Py = 4;
constexpr const ll W = ( 1000 / Px ) + 1;
constexpr const ll H = ( 1000 / Py ) + 1;
constexpr const ll P = Px * Py;
constexpr const ll NM = N + M;
constexpr const ll path_lim = 100;
constexpr const ll f_lim = 10000000000;
CIN( ll , N_dummy );
CIN( ll , M_dummy );
ll a[NM];
ll b[NM];
ll p[NM];
ll m[P][NM];
ll m_size[P] = {};
FOR_LL( num , 0 , N ){
CIN( ll , a_num );
CIN( ll , b_num );
SetAB( a_num , b_num );
}
ll E[NM][NM];
FOR_LL( i , 0 , N ){
ll (&Ei)[NM] = E[i];
FOR_LL( j , 0 , i ){
ll dx = a[i] - a[j];
ll dy = b[i] - b[j];
Ei[j] = E[j][i] = ( dx * dx + dy * dy ) * 25;
}
}
ll E_min[P][P];
ll near[P][P][2];
SetNear;
FOR_LL( num , N , NM ){
ll E_min_max = 0;
ll k_max;
ll h_max;
FOR_LL( k , 0 , P ){
if( m_size[k] > 0 ){
ll (&E_min_k)[P] = E_min[k];
ll k_plus = k + 1;
FOR_LL( h , 0 , k_plus ){
if( m_size[h] > 0 ){
ll& E_min_kh = E_min_k[h];
if( E_min_max < E_min_kh ){
E_min_max = E_min_kh;
k_max = k;
h_max = h;
}
}
}
}
}
ll E_min_max_min = 50000025;
ll x_min;
ll y_min;
ll (&near_kh)[2] = near[k_max][h_max];
ll& i_min = near_kh[0];
ll& j_min = near_kh[1];
FOR_LL( x , 0 , 1001 ){
FOR_LL( y , 0 , 1001 ){
ll dix = a[i_min] - x;
ll diy = b[i_min] - y;
ll djx = a[j_min] - x;
ll djy = b[j_min] - y;
ll E_min_max_yx = ( dix * dix + diy * diy ) * ( i_min < N ? 5 : 1 ) + ( djx * djx + djy * djy ) * ( j_min < N ? 5 : 1 );
if( E_min_max_min > E_min_max_yx ){
E_min_max_min = E_min_max_yx;
x_min = x;
y_min = y;
}
}
}
cout << x_min << " " << y_min << endl;
SetAB( x_min , y_min );
ll num_plus = num + 1;
FOR_LL( i , N , num_plus ){
ll (&Ei)[NM] = E[i];
FOR_LL( j , 0 , i ){
ll dx = a[i] - a[j];
ll dy = b[i] - b[j];
Ei[j] = E[j][i] = ( dx * dx + dy * dy ) * ( j < N ? 5 : 1 );
}
}
SetNear;
}
ll P_valid = 0;
ll k_valid[P];
FOR_LL( k , 0 , P ){
if( m_size[k] > 0 ){
k_valid[P_valid] = k;
}
P_valid++;
}
ll path[NM][NM][path_lim];
ll path_length[NM][NM];
ll path_E[NM][NM];
bool computed_path_E[NM][NM] = {};
FOR_LL( k , 0 , P_valid ){
ll (&m_k)[NM] = m[k_valid[k]];
ll& m_size_k = m_size[k_valid[k]];
// 手抜き
ll length_lim = max( m_size_k + 3 , (ll)10 );
if( m_size_k == 1 ){
ll& m_ki = m_k[0];
path[m_ki][m_ki][0] = m_ki;
path_length[m_ki][m_ki] = 1;
path_E[m_ki][m_ki] = 0;
computed_path_E[0][0] = true;
} else if( m_size_k > 1 ){
ll count = 0;
FOR_LL( length , m_size_k , length_lim ){
ll f_min = 1;
FOR_LL( i , 0 , length ){
f_min *= m_size_k;
}
f_min--;
if( f_min >= f_lim ){
length = length_lim;
}
FOR_LL( f , f_min , f_lim ){
ll f_copy = f;
ll path_current[path_lim];
bool used[NM] = {};
ll length_current = 0;
ll i_start = f_copy % m_size_k;
path_current[length_current] = i_start;
used[i_start] = true;
f_copy /= m_size_k;
length_current++;
while( length_current < length ){
ll i = f_copy % m_size_k;
if( i != path_current[length_current - 1] ){
path_current[length_current] = i;
used[i] = true;
f_copy /= m_size_k;
length_current++;
} else {
f_copy = 0;
length_current = length;
}
}
if( f_copy > m_size_k ){
f = f_lim;
} else if( f_copy != 0 ){
bool used_all = true;
FOR_LL( i , 0 , m_size_k ){
if( ! used[i] ){
used_all = false;
i = m_size_k;
}
}
if( used_all ){
ll path_E_current = 0;
FOR_LL( i , 1 , length ){
ll& m_ki = m_k[path_current[i]];
ll& m_kj = m_k[path_current[i - 1]];
path_E_current += E[m_ki][m_kj];
}
ll& i_finish = path_current[length - 1];
bool& computed_path_E_ij = computed_path_E[i_start][i_finish];
ll& path_E_ij = path_E[i_start][i_finish];
if( computed_path_E_ij ? path_E_ij > path_E_current : true ){
path_E_ij = path_E[i_finish][i_start] = path_E_current;
ll (&path_ij)[path_lim] = path[i_start][i_finish];
ll (&path_ji)[path_lim] = path[i_finish][i_start];
FOR_LL( i , 0 , length ){
path_ij[i] = path_current[i];
path_ji[i] = path_current[length - 1 - i];
}
path_length[i_start][i_finish] = path_length[i_finish][i_start] = length;
if( ! computed_path_E_ij ){
computed_path_E_ij = computed_path_E[i_finish][i_start] = true;
}
}
count++;
if( count == 10000 ){
length = length_lim;
}
}
}
}
}
}
}
ll E_sum_min = 50000025 * P;
ll k_start = p[0];
ll k_min = k_start;
ll k_mid_min[P];
FOR_LL( k_next , 0 , P_valid ){
ll& k = k_valid[k_next];
if( k != k_start ){
ll s = S;
s ^= ( 1 << k_start );
s ^= ( 1 << k );
ll k_mid[P];
ll E_sum = HeldKarp<NM,P>( k_start , k , 0 , k_valid , P_valid , path_E , near , E_min , k_mid );
E_sum += HeldKarp<NM,P>( k , k_start , s , k_valid , P_valid , path_E , near , E_min , k_mid );
E_sum += path_E[near[k_start][k][0]][near[k_mid[P_valid - 2]][k_start][1]] + path_E[near[k_start][k][1]][near[k][k_mid[1]][0]];
if( E_sum_min > E_sum ){
E_sum_min = E_sum;
k_min = k;
FOR_LL( k , 0 , P_valid ){
k_mid_min[k] = k_mid[k];
}
}
}
}
ll P_valid_minus = P_valid - 1;
ll& near_k_start_0 = P_valid == 1 ? P_valid_minus : near[k_mid_min[P_valid - 2]][k_start][1];
ll& near_k_start_1 = P_valid == 1 ? P_valid_minus : near[k_start][k_min][0];
ll (&path_k_start)[path_lim] = path[near_k_start_0][near_k_start_1];
ll& path_length_k_start = path_length[near_k_start_0][near_k_start_1];
ll num_start;
FOR_LL( num , 0 , path_length_k_start ){
if( path_k_start[num] == 0 ){
num_start = num;
num = path_length_k_start;
}
}
ll V = path_length_k_start;
FOR_LL( k , 0 , P_valid_minus ){
ll& k_mid_min_k = k_mid_min[k];
ll& near_k_0 = near[k_mid_min[( k + P_valid_minus ) % P_valid ]][k_mid_min_k][1];
ll& near_k_1 = near[k_mid_min_k][k_mid_min[k+1]][0];
V += path_length[near_k_0][near_k_1];
}
cout << V << endl;
FOR_LL( num , num_start , path_length_k_start ){
ll& i = path_k_start[num];
if( i < N ){
cout << 1 << " " << i << endl;
} else {
cout << 2 << " " << i - N << endl;
}
}
FOR_LL( k , 0 , P_valid_minus ){
ll& k_mid_min_k = k_mid_min[k];
ll& near_k_0 = near[k_mid_min[( k + P_valid_minus ) % P_valid ]][k_mid_min_k][1];
ll& near_k_1 = near[k_mid_min_k][k_mid_min[k+1]][0];
ll (&path_k)[path_lim] = path[near_k_0][near_k_1];
ll& path_length_k = path_length[near_k_0][near_k_1];
FOR_LL( num , 0 , path_length_k ){
ll& i = path_k[num];
if( i < N ){
cout << 1 << " " << i << endl;
} else {
cout << 2 << " " << i - N << endl;
}
}
}
FOR_LL( num , 0 , num_start ){
ll& i = path_k_start[num];
if( i < N ){
cout << 1 << " " << i << endl;
} else {
cout << 2 << " " << i - N << endl;
}
}
return 0;
}
template <ll NM , ll P>
const ll& HeldKarp( const ll& k_start , const ll& k_goal , const ll& s , const ll (&k_valid)[P] , const ll& P_valid , const ll (&path_E)[NM][NM] , const ll (&near)[P][P][2] , const ll (&E_min)[P][P] , ll (&k_mid)[P] )
{
static ll answer_E[P][P][S];
static ll answer_mid[P][P][P];
static bool solved[P][P][S];
ll (&answer_mid_kskg)[P] = answer_mid[k_start][k_goal];
if( solved[k_start][k_goal][s] ){
ll P_valid_minus = P_valid - 1;
FOR_LL( k , 0 , P_valid_minus ){
k_mid[k] = answer_mid_kskg[k];
}
return answer_E[k_start][k_goal][s];
}
if( s == 0 ){
k_mid[0] = answer_mid_kskg[0] = k_start;
k_mid[1] = answer_mid_kskg[1] = k_goal;
solved[k_start][k_goal][s] = true;
return answer_E[k_start][k_goal][s] = answer_E[k_goal][k_start][s] = E_min[k_start][k_goal];
}
ll s_copy = s;
ll card = 0;
ll k_s[P];
ll k_s_i = 0;
while( s_copy != 0 ){
if( s_copy % 2 == 1 ){
k_s[card] = k_s_i;
card++;
}
k_s_i++;
}
ll E_current_min = 7500003751;
ll k_mid_current_min[P];
ll k_mid_current[P];
ll card_plus = card + 1;
FOR_LL( i , 0 , card ){
ll& k = k_s[i];
ll E_current = HeldKarp<NM,P>( k_start , k , 0 , k_valid , P_valid , path_E , near , E_min , k_mid );
E_current += HeldKarp<NM,P>( k_start , k , s ^ ( 1 << k ) , k_valid , P_valid , path_E , near , E_min , k_mid_current );
E_current += path_E[near[k_start][k][1]][near[k][k_mid_current[1]][0]];
if( E_current_min < E_current ){
E_current_min = E_current;
FOR_LL( j , 0 , card_plus ){
k_mid_current_min[j] = k_mid_current[j];
}
}
}
answer_mid_kskg[0] = k_start;
FOR_LL( i , 0 , card_plus ){
answer_mid_kskg[i+1] = k_mid[i+1] = k_mid_current_min[i];
}
solved[k_start][k_goal][s] = true;
return answer_E[k_start][k_goal][s] = answer_E[k_goal][k_start][s] = E_current_min;
}