mayoko’s diary

プロコンとかいろいろ。

SRM 480 div1 easy: InternetSecurity

これ英語読めない日本人には厳しすぎる…

解法

やるだけ。

stringstream 使うとなんとなく簡単に書けます。

bool done[55];

class InternetSecurity {
public:
    vector <string> determineWebsite(vector <string> address, vector <string> keyword, vector <string> danger, int threshold) {
        vector<pair<int, string> > ans;
        int n = address.size();
        set<string> dangerous;
        for (string t : danger) dangerous.insert(t);
        memset(done, false, sizeof(done));
        while (1) {
            bool finish = true;
            for (int i = 0; i < n; i++) {
                if (done[i]) continue;
                stringstream ss(keyword[i]);
                string s;
                int cnt = 0;
                while (ss >> s) {
                    bool ng = false;
                    for (string t : dangerous) {
                        if (s == t) ng = true;
                    }
                    if (ng) cnt++;
                }
                if (cnt >= threshold) {
                    ans.emplace_back(i, address[i]);
                    stringstream ss(keyword[i]);
                    string s;
                    while (ss >> s) {
                        dangerous.insert(s);
                    }
                    done[i] = true;
                    finish = false;
                }
            }
            if (finish) break;
        }
        vector<string> ret;
        sort(ans.begin(), ans.end());
        for (auto p : ans) ret.push_back(p.second);
        return ret;
    }
};