Codeforces #203, Division 2, B : Resort

問題文

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

概要

N 頂点からなる有向グラフがあり、各頂点には 0 または 1 の属性が付与されている。
各頂点について、それを終点とする辺の始点が与えられる。
次の条件を満たすパスの内、長さが最大のものを一つ出力せよ。

1. パスの長さを k とする
2. 1 番目から k - 1 番目の頂点の属性は 0 である
3. k 番目の頂点の属性は 1 である
4. 終点以外の任意の頂点を始点とする辺は一本しかない

解法

終点側から多点スタートで探索＋経路復元しました。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

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

	int n;
	cin >> n;

	VI types( n ), as( n ), counts( n );
	FOR( t, types )
	{
		cin >> t;
	}
	FOR( a, as )
	{
		cin >> a;
		if ( a )
		{
			counts[ a - 1 ]++;
		}
	}

	VI dist( n, -1 ), next( n, -1 );
	queue<int> que;

	REP( i, 0, n )
	{
		if ( types[i] == 1 )
		{
			que.push( i );
			dist[i] = 0;
		}
	}

	while ( !que.empty() )
	{
		const int cur = que.front();
		que.pop();

		if ( counts[ as[ cur ] - 1 ] == 1 && dist[ as[ cur ] - 1 ] < dist[ cur ] + 1 && types[ as[ cur ] - 1 ] == 0 )
		{
			dist[ as[ cur ] - 1 ] = dist[ cur ] + 1;
			next[ as[ cur ] - 1 ] = cur;
			que.push( as[ cur ] - 1 );
		}
	}

	int v = max_element( ALL( dist ) ) - dist.begin();

	VI res;
	while ( v != -1 )
	{
		res.PB( v + 1 );
		v = next[v];
	}

	cout << res.size() << endl;
	REP( i, 0, res.size() )
	{
		cout << res[i] << ( i + 1 < res.size() ? ' ' : '\n' );
	}
	cout << flush;		

	return 0;
}