Good Bye 2014, B : New Year Permutation

問題文

　http://codeforces.com/contest/500/problem/B

問題概要

　サイズ の順列 及び， 行列 が与えられる．また， 及び が成り立つ．
　二つの整数 について， であるときに限り， と を交換することができる．任意回の操作で作ることができる列の内，辞書式順序で最小のものを求めよ．

解法

　 に関する制約より，要素の移動には推移律と対称律が成り立ちます．すなわち，3 つの整数 について， に移動可能且つ に移動可能なとき， も移動可能であり，また，2 つの整数 について， に移動可能ならば にも移動可能です．このことから，到達可能な範囲に要素を移動させる限り，任意の位置に移動させることが可能だと分かります．
　辞書式順序の特性を踏まえると，より小さい要素をできる限り手前に配置するのが最適になるので，各要素について到達可能な範囲を求めてから，小さい要素から順に可能な限り手前に移動させるように操作することで，辞書式順序で最小となる列をつくることができます．
　各要素の到達可能な範囲を求めるには，Warshall-Floyd 法を利用することができます．

コード

using VI = vector< int >;
using VVI = vector< VI >;
using VS = vector< string >;

template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }
template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i=0; i<v.size(); ++i ){ s << (" "+!i) << v[i]; } return s; }

#define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define BI back_inserter

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int N;
	cin >> N;

	VI P( N );
	cin >> P;

	VVI A( N );
	{
		VS board( N );
		cin >> board;

		REP( i, 0, N )
		{
			transform( ALL( board[i] ), BI( A[i] ), bind( equal_to< char >(), _1, '1' ) );
		}
	}
	REP( i, 0, N )
	{
		A[i][i] = 1;
	}

	REP( k, 0, N )
	{
		REP( i, 0, N )
		{
			REP( j, 0, N )
			{
				A[i][j] |= A[i][k] && A[k][j];
			}
		}
	}

	VI pos( N + 1 );
	REP( i, 0, N )
	{
		pos[ P[i] ] = i;
	}

	VI res( N, -1 );
	REP( t, 1, N + 1 )
	{
		int p = pos[t];
		REP( i, 0, N )
		{
			if ( A[p][i] && res[i] == -1 )
			{
				res[i] = t;
				break;
			}
		}
	}

	cout << res << endl;

	return 0;
}