SRM474 Div1 Easy(250), Div2 Medium(500) RouteIntersection

TopCoder

RouteIntersection

頂点数が高々50なので、実際に動く次元の数も高々50。

#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;

class RouteIntersection
{
public:
    string isValid( int N, vector <int> coords, string moves );
};

string RouteIntersection::isValid( int N, vector <int> coords, string moves )
{
    int n = (int)coords.size();

    map<int,int> p;
    set<map<int,int> > hist;
    hist.insert( p );

    for ( int i=0; i<n; i++ )
    {
        if ( moves[i] == '+' )  p[coords[i]]++;
        if ( moves[i] == '-' )  p[coords[i]]--;

        if ( p[coords[i]] == 0 )
            p.erase( coords[i] );

        hist.insert( p );
    }

    return (int)hist.size()==n+1 ? "VALID" : "NOT VALID";
}