SRM525 Div1 Medium(525) Rumor

Rumor

聞いた噂はなるべく広めたほうが良いし、１度広めた噂をもう1度広める意味は無いので、噂の広がるスピードを決めるのは、両方の噂を同時に聞いた場合に次のステップでどちらを広めるかということのみ。N≦16なので、それぞれのウサギがどちらの噂を先に広めるか、2^N通りを全て試す。

#include <string>
#include <vector>
using namespace std;

class Rumor{public:
int getMinimum( string knowledge, vector <string> graph )
{
    int N = (int)knowledge.size();

    int ans = -1;

    for ( int b=0; b<1<<N; b++ )
    {
        vector<int> r[2];
        r[0].resize(N,-1);
        r[1].resize(N,-1);

        for ( int i=0; i<N; i++ )
            if ( knowledge[i]=='Y' )
                r[0][i] = r[1][i] = 0;

        for ( int i=0; i<N; i++ )
        {
            for ( int j=0; j<N; j++ )
            {
                int t = -1;
                if ( r[0][j]!=r[1][j] )
                {
                    if ( r[0][j]==i )
                        t = 0;
                    if ( r[1][j]==i )
                        t = 1;
                }
                if ( r[0][j]>=0 && r[0][j]==r[1][j] )
                {
                    if ( r[0][j]==i )
                        t = b>>j&1;
                    if ( r[0][j]==i-1 )
                        t = 1-(b>>j&1);
                }

                if ( t!=-1 )
                    for ( int k=0; k<N; k++ )
                        if ( graph[j][k]=='Y' && r[t][k]==-1 )
                            r[t][k] = i+1;
            }
        }

        int a = 0;
        bool f = true;
        for ( int i=0; i<N; i++ )
        {
            a = max( a, r[0][i] );
            a = max( a, r[1][i] );
            if ( r[0][i]==-1 || r[1][i]==-1 )
                f = false;
        }
        if ( f && ( ans==-1 || ans>a ) )
            ans = a;
    }

    return ans;
}};