SRM480 Div1 Easy(250), Div2 Medium(500) InternetSecurity

InternetSecurity

アルゴリズムが書かれているので、その通りに実装する。

#include <vector>
#include <string>
#include <set>
#include <sstream>

using namespace std;

class InternetSecurity{public:
vector <string> determineWebsite( vector <string> address, vector <string> keyword, vector <string> dangerous, int threshold )
{
    int N = (int)address.size();

    vector<vector<string> > word( N );
    for ( int i=0; i<N; i++ )
    {
        stringstream ss( keyword[i] );
        string t;
        while ( ss >> t )
            word[i].push_back( t );
    }
    set<string> danger( dangerous.begin(), dangerous.end() );
    vector<bool> site( N, false );

    bool up;
    do
    {
        up = false;
        
        for ( int i=0; i<N; i++ )
        if ( ! site[i] )
        {
            int c = 0;
            for ( vector<string>::iterator w=word[i].begin();
                  w!=word[i].end(); w++ )
                if ( danger.count( *w ) > 0 )
                    c++;

            if ( c >= threshold )
            {
                site[i] = true;
                for ( vector<string>::iterator w=word[i].begin();
                      w!=word[i].end(); w++ )
                    danger.insert( *w );
                up = true;
            }
        }
    }
    while ( up );

    vector<string> answer;
    for ( int i=0; i<N; i++ )
        if ( site[i] )
            answer.push_back( address[i] );

    return answer;
}
};