domains

#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>
#include <string_view>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <cassert>

using namespace std;

// узел префиксного дерева, https://ru.algorithmica.org/cs/string-structures/trie/
struct Node {
    unordered_map<char, Node*> childs;
};

class Domain {
public:
    explicit Domain(const string& domain) {
        domain_ = {domain.crbegin(), domain.crend()};
        // точка в начале домена нужна на такой случай запрещенных доменов: cpp.ru и p.ru
        // она разделит эти случаи на ветки: а) u--r--.--p--. б) u--r--.--p--p--c--.
        // иначе же будет одна ветка u--r--.--p--p--c
        domain_.push_back('.');
    }

    bool operator==(const Domain& other) const {
        return domain_ == other.domain_;
    }

    bool operator<(const Domain& other) const {
        return domain_ < other.domain_;
    }

    // Принимает другой домен и возвращающий true, если this его поддомен
    bool IsSubdomain(const Domain& other) const {
        const string& other_domain = other.Get();

        if (domain_.size() > other_domain.size()) {
            // не может this быть поддоменом, если this длиннее
            return false;
        }

        // если this не длиннее, значит он меньше или равен,
        // тогда обрежем other по this
        const string new_other = other.domain_.substr(0, domain_.size());

        return domain_ == new_other;
    }

    const string& Get() const {
        return domain_;
    }

private:
    string domain_ = ""s;
};

class DomainChecker {
public:
    // конструктор принимает список запрещённых доменов через пару итераторов
    template<typename InputIt>
    explicit DomainChecker(InputIt first, InputIt last) {
        vector<Domain> processed_domains = {first, last};
        sort(processed_domains.begin(), processed_domains.end());

        // в запрещенных доменах префиксного дерева плоха та ситуация, когда
        // один домен есть поддоммен другого домена; например, когда:
        // 1) cpp.ru и ru -- эта ситуация исключается unique
        // 2) cpp.ru и p.ru -- эта ситуация исключается вставкой точки в начало домена

        // если ситуацию 1) не обработать, нельзя будет понять для сайта
        // python.ru запрещен ли он, потому что нельзя понять:
        // - ru это один из запрещенных доментов?
        // - или это часть запрещенного домена?
        // если ситуацию 2) не предусмотреть, в дереве запрещенной будет только одна
        // ветка u--r--.--p--p--c-- вместо двух положенных веток
              // u--r--.--p--p--c--.
              // u--r--.--p--.

        auto last_unique = unique(processed_domains.begin(), processed_domains.end(),
                            [](const Domain& lhs, const Domain& rhs) {
                                return lhs.IsSubdomain(rhs);
                            });

        root_ = new Node();

        for (auto domain_it = processed_domains.begin(); domain_it != last_unique; ++domain_it) {
            Node* tmp_root = root_;
            const string& domain_name = domain_it->Get();

            for (auto char_it = domain_name.cbegin(); char_it != domain_name.cend(); ++char_it) {
                char c = *char_it;
                if (tmp_root->childs.count(c) == 0) {
                    auto node = new Node;
                    all_nodes_to_delete_.push_back(node);

                    tmp_root->childs[c] = node;
                    tmp_root = node;
                } else {
                    tmp_root = tmp_root->childs[c];
                }
            }
        }
    }

    // удалит все узлы, созданные в куче
    ~DomainChecker() {
        for (Node* node_to_delete : all_nodes_to_delete_) {
            delete node_to_delete;
        }

        delete root_;
    }

    // IsForbidden, вернет true, если домен запрещён
    bool IsForbidden(const Domain& domain) {

        // запрещенных доменов нет, значит ничто не запрещено
        if (root_->childs.size() == 0) {
            return false;
        }
        // домен domain будет запрещенным, если какой-то запрещенный домен является его суффиксом, например:
        // запрещенный рф.ru и домены one.рф.ru, two.рф.ru, но не
        // запрещенный рф.ru и домены oneрф.ru, twoрф.ru

        const string& domain_to_check = domain.Get();
        Node* tmp_root = root_;

        // проверяем, есть ли цепочка символов domain_to_check в какой-то ветке дереве запрещенных доменов
        for (auto it = domain_to_check.begin(); it != domain_to_check.end(); ++it) {

            if (tmp_root->childs.size() == 0) {
                // ветка дерева закончилась, значит она является суффиксом проверяемого домена
                return true;
            } else if (tmp_root->childs.count(*it) == 0) {
                // символа из проверяемого домена нет в ветке дерева
                return false;
            }

            // символ из проверяемого домена есть в подходящем запрещенном домене,
            // берем детей этого символа и на следующей итерации история повторится
            tmp_root = tmp_root->childs.at(*it);
        }

        if (tmp_root->childs.size() > 0) {
            return false;
        }

        return true; // эквивалентно tmp_root->childs.size() == 0
    }

    // сделан для тестирования
    bool IsForbidden(const string& domain) {
        return IsForbidden(Domain{domain});
    }

private:
    Node* root_;
    vector<Node*> all_nodes_to_delete_;
};

// ReadNumberOnLine считывает число из строки
template <typename Number>
Number ReadNumberOnLine(istream& input) {
    string line;
    getline(input, line);

    Number num;
    std::istringstream(line) >> num;

    return num;
}

// ReadDomains читает заданное количество доменов из стандартного входа
vector<Domain> ReadDomains(istream& input, size_t lines) {
    string domain;
    vector<Domain> forbidden_domains;

    for (size_t line = 0; line < lines; ++line) {
        getline(input, domain);
        forbidden_domains.emplace_back(domain);
    }

    return forbidden_domains;
}

void YandexTest() {
    stringstream stream;

    stream << "4\n"s
              "gdz.ru\n"
              "maps.me\n"
              "m.gdz.ru\n"
              "com\n";

    const std::vector<Domain> raw_forbidden_domains = ReadDomains(stream, ReadNumberOnLine<size_t>(stream));
    DomainChecker checker(raw_forbidden_domains.begin(), raw_forbidden_domains.end());

    assert(checker.IsForbidden("gdz.ru"s));
    assert(checker.IsForbidden("gdz.com"s));
    assert(checker.IsForbidden("m.maps.me"s));
    assert(checker.IsForbidden("alg.m.gdz.ru"s));
    assert(checker.IsForbidden("maps.com"s));
    assert(!checker.IsForbidden("maps.ru"s));
    assert(!checker.IsForbidden("gdz.ua"s));
}

void MyTest() {
    stringstream stream;

    stream << "8\n"
              "js.fr\n"
              "ts.js.fr\n"
              "com\n"
              "hello.com\n"
              "abacaba.rf\n"
              "hello.world\n"
              "y.sva.yl.mvs.cp.yww\n" // хитрый тест
              "hsr.oxay.sva.yl.mvs.cp.yww\n"; // если этот домен запрещен

    const std::vector<Domain> raw_forbidden_domains = ReadDomains(stream, ReadNumberOnLine<size_t>(stream));
    DomainChecker checker(raw_forbidden_domains.begin(), raw_forbidden_domains.end());

    // проверка, что сами запрещенные домены являются запрещенными
    assert(checker.IsForbidden("js.fr"s));
    assert(checker.IsForbidden("ts.js.fr"s));
    assert(checker.IsForbidden("com"s));
    assert(checker.IsForbidden("hello.com"s));
    assert(checker.IsForbidden("abacaba.rf"s));
    assert(checker.IsForbidden("hello.world"s));
    assert(checker.IsForbidden("y.sva.yl.mvs.cp.yww"s)); // хитрый тест

    // проверка, что их поддомены являются запрещенными
    assert(checker.IsForbidden("ans.com"s));
    assert(checker.IsForbidden("hello.yandex.com"s));
    assert(checker.IsForbidden("some.subdomain.for.js.fr"s));
    assert(checker.IsForbidden("baca.baca.baca.baca.baca.abacaba.rf"s));
    assert(checker.IsForbidden("good-morning.tonight.yello.hello.world"s));

    // проверка, что НЕ поддомены не являются запрещенными
    assert(!checker.IsForbidden("s.fr"s));
    assert(!checker.IsForbidden("csharp.fr"s));
    assert(!checker.IsForbidden("ans.dotcom"s));
    assert(!checker.IsForbidden("acaba.rf"s));
    assert(!checker.IsForbidden("caba.rf"s));
    assert(!checker.IsForbidden("_ello.world"s));
}

void SubDomainTest() {
    assert(Domain{"ru"s}.IsSubdomain(Domain{"abc.ru"s}));
    assert(Domain{"abc.ru"s}.IsSubdomain(Domain{"abc.ru"s}));
    assert(!Domain{"abc.ru"s}.IsSubdomain(Domain{"ru"s}));

    assert(!Domain{"com"s}.IsSubdomain(Domain{"ans.dotcom"s}));

    assert(Domain{"com"s}.IsSubdomain(Domain{"ans.com"s}));
}

void OperatorEqualDomainTest() {
    assert(Domain{"afgbjsbfkjhblhblfh"s} == Domain("afgbjsbfkjhblhblfh"s));
    assert(Domain{"rf.rf.rf"s} == Domain("rf.rf.rf"s));
    assert(!(Domain{"hello.rf"s} == Domain("hello.rt"s)));
}

void ReadDomainsTest() {
    stringstream stream;

    stream << "6\n"
              "js.fr\n"
              "ts.js.fr\n"
              "com\n"
              "hello.com\n"
              "abacaba.rf\n"
              "hello.world\n";

    const std::vector<Domain> domains = ReadDomains(stream, ReadNumberOnLine<size_t>(stream));

    assert(domains[0] == Domain{"js.fr"s});
    assert(domains[1] == Domain{"ts.js.fr"s});
    assert(domains[2] == Domain{"com"s});
    assert(domains[3] == Domain{"hello.com"s});
    assert(domains[4] == Domain{"abacaba.rf"s});
    assert(domains[5] == Domain{"hello.world"s});
}

void Test() {
    ReadDomainsTest();
    OperatorEqualDomainTest();
    SubDomainTest();
    YandexTest();
    MyTest();

    // cout << __PRETTY_FUNCTION__ << " OK"sv << endl;
}

int main() {
    Test();

    const std::vector<Domain> raw_forbidden_domains = ReadDomains(cin, ReadNumberOnLine<size_t>(cin));

    DomainChecker checker(raw_forbidden_domains.begin(), raw_forbidden_domains.end());

    const std::vector<Domain> test_domains = ReadDomains(cin, ReadNumberOnLine<size_t>(cin));

    for (const Domain& domain : test_domains) {
        cout << (checker.IsForbidden(domain) ? "Bad"s : "Good"s) << endl;
    }
}