torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #187, Division 2, A : Sereja and Bottles

概要

N 個の瓶があり、それぞれの瓶のメーカーは a_i であり、それを用いて他の b_i 製の瓶を開けることができる。
(開けるのに使う瓶は必ずしも開いていなくてもよい)
開けられない瓶の数を求めよ。

解法

b_i = a_j (ただし i \neq j) となる i, j の組が一つでもあれば、i 番目の瓶を開けることができると分かります。
i, j についての二重ループで全通り試せば解けます。

コード

typedef vector<int> VI;

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

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

	int n;
	cin >> n;

	VI as( n ), bs( n );
	REP( i, 0, n )
	{
		cin >> as[i] >> bs[i];
	}

	vector<bool> openalbe( n, false );
	REP( i, 0, n )
	{
		REP( j, 0, n )
		{
			if ( i == j )
			{
				continue;
			}

			openalbe[j] = openalbe[j] | bs[i] == as[j];
		}
	}	

	cout << count( ALL( openalbe ), false ) << endl;

	return 0;
}