Submission #962044

#	Time	Username	Problem	Language	Result	Execution time	Memory
962044		riariti	CSS (COI14_css)	C++17	60 / 100	1449 ms	69460 KiB

css

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

struct HTMLelement {
    string id;
    set<int> classes;
    vector<int> children;
    HTMLelement() {}
    HTMLelement(char *name) : id(name) {}

    void add_child(int child_id) { children.push_back(child_id); }

    void add_class(char *str) {
        int hash = 0;
        for (char *ptr = str; *ptr; ++ptr)
            hash = hash * 71 + *ptr - 'a' + 1;
        classes.insert(hash);
    }
};

struct SelectorElement {
    int type;
    vector<int> classes;
    SelectorElement(int type) : type(type) {}

    void add_class(char *str) {
        int hash = 0;
        for (char *ptr = str; *ptr; ++ptr)
            hash = hash * 71 + *ptr - 'a' + 1;
        classes.push_back(hash);
    }

    bool check(const HTMLelement &E) {
        for (auto cls : classes)
            if (E.classes.find(cls) == E.classes.end())
                return 0;
        return 1;
    }
};

vector<HTMLelement> read_document(void) {
    int N;
    scanf("%d", &N);

    stack<int> ancestors;

    vector<HTMLelement> tree;
    tree.push_back(HTMLelement());
    ancestors.push(0);

    for (int i = 0; i < N; ++i) {
        char tag_start[11];
        scanf("%s", tag_start);
        if (strcmp(tag_start, "</div>") == 0) {
            ancestors.pop();
        } else {
            char name[31];
            scanf(" id='%[^']'", name);

            tree.push_back(HTMLelement(name));
            tree[ancestors.top()].add_child(tree.size() - 1);
            ancestors.push(tree.size() - 1);

            scanf(" class='");
            char class_name[31];
            while (scanf(" %[^ ']", class_name))
                tree.back().add_class(class_name);
            scanf("'>");
        }
    }

    return tree;
}

vector<SelectorElement> read_selector(void) {
    vector<SelectorElement> sel;

    char c;
    while (scanf("%c", &c)) {
        if (c == ' ')
            continue;
        if (c == '\n')
            break;
        if (c == '>') {
            sel.push_back(SelectorElement(0));
            scanf(" %c", &c);
        } else
            sel.push_back(SelectorElement(1));

        sel.push_back(SelectorElement(2));

        char class_name[21];
        while (scanf("%[^. \n]", class_name)) {
            sel.back().add_class(class_name);
            scanf(".");
        }
    }

    return sel;
}

vector<HTMLelement> DocumentTree;
vector<SelectorElement> Selector;
bool visited[2][5010][5010];

void dfs(int jump, int node, int pos, vector<int> &ans) {
    if (visited[jump][node][pos])
        return;
    visited[jump][node][pos] = 1;

    if (pos == Selector.size()) {
        if (!jump)
            ans.push_back(node);
        return;
    }

    if (Selector[pos].type == 0) {
        for (auto child : DocumentTree[node].children)
            dfs(0, child, pos + 1, ans);
    }

    if (Selector[pos].type == 1) {
        if (jump)
            dfs(0, node, pos + 1, ans);
        for (auto child : DocumentTree[node].children)
            dfs(1, child, pos, ans);
    }

    if (Selector[pos].type == 2) {
        if (!Selector[pos].check(DocumentTree[node]))
            return;
        dfs(0, node, pos + 1, ans);
    }
}

int main(void) {

    DocumentTree = read_document();

    int M;
    scanf("%d\n", &M);
    for (int i = 0; i < M; ++i) {
        Selector = read_selector();

        memset(visited, 0, sizeof visited);
        vector<int> ans;

        dfs(0, 0, 0, ans);

        printf("%d ", (int)ans.size());
        sort(ans.begin(), ans.end());
        for (auto id : ans)
            printf("%s ", DocumentTree[id].id.c_str());
        printf("\n");
    }

    return 0;
}

/*
#include <bits/stdc++.h>
#include <ios>

std::hash<std::string> HSH;
constexpr std::string END = "</div>";

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

#ifdef local
    std::freopen("css.in", "r", stdin);
#endif

    int N;
    std::cin >> N;
    std::vector<std::string> DOC(N);
    std::cin.ignore();
    for (auto &s : DOC) {
        std::getline(std::cin, s);
    }
    int M;
    std::cin >> M;
    std::vector<std::string> QRY(M);
    std::cin.ignore();
    for (auto &s : QRY) {
        std::getline(std::cin, s);
    }

    // each HTML line
    struct HTML {
        std::string id;
        std::set<int> cls;
        std::vector<int> chd;

        HTML() = default;
        explicit HTML(std::string &_id) : id(_id) {}

        void add_child(int ch) { chd.push_back(ch); }

        void add_class(const std::string &x) { cls.insert(HSH(x)); }

        // checkif certain class is here on this HTML line
        bool available_class(int css) const { return cls.count(css); }
    };

    auto get_id_class = [&](const std::string &s)
        -> std::pair<std::string, std::vector<std::string>> {
        constexpr std::size_t SQ = 4;

        std::array<int, SQ> sq;
        std::fill(sq.begin(), sq.end(), -1);

        for (int i = 0; i < s.size(); i++) {
            if (s[i] != '\'') {
                continue;
            }

            for (int j = 0; j < SQ; j++) {
                if (sq[j] != -1) {
                    continue;
                }

                sq[j] = i;
                break;
            }
        }

        std::string nme;
        for (int i = sq[0] + 1; i <= sq[1] - 1; i++) {
            nme += s[i];
        }

        std::vector<std::string> cls;
        std::string tmp;
        for (int i = sq[2] + 1; i <= sq[3] - 1; i++) {
            if (s[i] != ' ') {
                tmp += s[i];
                continue;
            }

            cls.push_back(tmp);
            tmp = "";
        }
        cls.push_back(tmp);

        return {nme, cls};
    };

    std::vector<HTML> adj{HTML()};
    {
        // idx stack just like mine below
        std::stack<int> st;
        st.push(0);

        for (int i = 0; i < N; i++) {
            if (DOC[i] == END) {
                assert(!st.empty());
                st.pop();
                continue;
            }

            auto [id, cls] = get_id_class(DOC[i]);

            adj.push_back(HTML(id));
            // parent
            auto j = adj.size() - 1;
            // j and not i => since some of them have the END
            adj[st.top()].add_child(j);
            st.push(j);

            for (auto x : cls) {
                adj.back().add_class(x);
            }
        }
    }

    // CSS selectors
    struct CSS {
        int typ;
        std::vector<std::size_t> cls;

        CSS() = default;
        explicit CSS(int _typ) : typ(_typ) {}

        void add_class(const std::string &x) { cls.push_back(HSH(x)); }

        bool check(const HTML &h) {
            // check that all classes exist in that line of html code

            for (auto c : cls) {
                if (!h.available_class(c)) {
                    return false;
                }
            }

            return true;
        }
    };

    auto parse_css = [&](const std::string &s) {
        std::vector<CSS> qry(M);
        std::stringstream ss(s);
        for (char c; ss >> std::noskipws >> c;) {
            if (c == ' ') {
                continue;
            }
            if (c == '\n') {
                break;
            }

            if (c == '>') {
                // can not skip this place!!!
                qry.push_back(CSS(0));
                // space
                std::cin >> c;
            } else {
                // anything else so can skip it without any worry
                qry.push_back(CSS(1));
            }
            // next one should be the string / classes so check
            qry.push_back(CSS(2));

            std::string cn;
            while (std::cin >> cn && cn != "." && cn != " ") {
                qry.back().add_class(cn);
            }
        }

        return qry;
    };

    std::vector vis(2, std::vector(N + 1, std::vector<bool>(M + 1)));
    std::vector<int> ans;

    for (int i = 0; i < M; i++) {
        auto sel = parse_css(QRY[i]);

        // jump and no jump if '>' or '_' or '.'
        auto dfs = [&](auto &&self, bool jmp, int i, int j) -> void {
            if (vis[jmp][i][j]) {
                return;
            }

            vis[jmp][i][i] = true;

            if (j == sel.size()) {
                // no jump so take it
                if (!jmp) {
                    ans.push_back(i);
                }

                return;
            }

            if (sel[j].typ == 0) {
                // have to check the children (id / html) explicitly (hence no
                // jump) if they ahve the class
                for (auto c : adj[i].chd) {
                    self(self, 0, c, j + 1);
                }
            } else if (sel[j].typ == 1) {
                // do anything basically
                // if you have jump (dont jump next and jump)
                // other wise alsways jump
                //
                // you have choice of jumping (from the previous other non-'>'
                // char)
                if (jmp) {
                    // then you have to check the next one
                    // and also dont

                    // jumped so skip, bye bye
                    self(self, 0, i, j + 1);
                }

                for (auto c : adj[i].chd) {
                    self(self, 1, c, j);
                }
            } else {
                assert(sel[j].typ == 2);
                // basically check here if the current html node (i)
                // contains these classes, if not this does not work so go back
                // dont jump sicne next can be a class
                //
                // so now check if this HTML line contains the classes

                if (!sel[j].check(adj[i])) {
                    return;
                }

                // j + 1=> next class / char to check
                // i since same (this is just for checking)
                self(self, 0, i, j + 1);
            }
        };
        dfs(dfs, 0, 0, 0);

        std::ranges::sort(ans);
        for (auto i : ans) {
            std::cout << adj[i].id << " ";
        }
        std::cout << "\n";

        vis.assign(2, std::vector(N + 1, std::vector<bool>(M + 1)));
        ans.clear();
    }

    /*
    std::map<std::string, int> cc;
    std::vector<std::string> cv;
    auto compress = [&](const std::string &s) {
        if (!cc.count(s)) {
            std::cerr << "err\n";
            std::exit(1);
        }

        return cc[s];
    };
    auto expand = [&](int i) { return cv[i]; };

    std::vector<int> id(N);
    std::vector<std::vector<int>> cls(N);
    auto parse_html = [&]() {


        for (int i = 0; i < N; i++) {
            auto [nme, cls] = get_id_class(DOC[i]);

            cv.push_back(nme);

            for (auto x : cls) {
                cv.push_back(x);
            }
        }
        {
            std::set st(cv.begin(), cv.end());
            cv = std::vector(st.begin(), st.end());
        }
        for (int i = 0; i < cv.size(); i++) {
            cc[cv[i]] = i;
        }

        for (int i = 0; i < N; i++) {
            auto [nme, cs] = get_id_class(DOC[i]);
            id[i] = compress(nme);

            std::vector<int> tmp;
            for (auto &x : cs) {
                tmp.push_back(compress(x));
            }

            cls[i] = std::move(tmp);
        }
    };
    parse_html();

    const std::string END = "</div>";

    struct HTML {
        int id;
        std::set<int> cls;
        std::vector<int> chd;

        void add_edge(int chi) { chd.push_back(chi); }

        void add_class(int ch) { cls.insert(ch); }
    };
    std::vector<HTML> adj;

    auto parse_css = [&]() {

    };
    parse_css();

    struct CSS {};

    return 0;
}

/*
#include <bits/stdc++.h>



int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

#ifdef local
    std::freopen("css.in", "r", stdin);
#endif

    std::map<int, int> id;
    std::map<int, std::vector<int>> cl;
    std::map<int, bool> end;
    for (int i = 0; i < N; i++) {
        auto &x = DOC[i];
        if (x == END) {
            end[i] = true;
            continue;
        }

        auto [nme, cls] = get_id_class(x);

        id[i] = compress(nme);

        std::vector<int> tmp;
        for (auto x : cls) {
            tmp.push_back(compress(x));
        }
        cl[i] = tmp;
    }

    std::vector<std::vector<int>> adj(N);
    std::stack<int> st;
    for (int i = 0; i < N; i++) {
        if (end[i]) {
            assert(!st.empty());

            st.pop();

            continue;
        }

        if (!st.empty()) {
            adj[st.top()].push_back(i);
        }

        st.push(i);
    }

    // for (int i = 0; i < N; i++) {
    //     std::cerr << id[i] << "\n";
    //     for (auto j : adj[i]) {
    //         std::cerr << id[j] << ", ";
    //     }
    //     std::cerr << "\n";
    // }

    // class - id
    std::map<int, std::vector<int>> cld;
    for (int i = 0; i < N; i++) {
        if (end[i]) {
            continue;
        }

        for (auto x : cl[i]) {
            cld[x].push_back(i);
        }
    }

    // ok space => descendant of curr node (not neceasarily children) got
this
    // but dont know how since naively check with dfs
    // > => did not understand intially => it is a children of the node
    // on the tree

    return 0;
}
*/

Compilation message (stderr)

css.cpp:416:5: warning: "/*" within comment [-Wcomment]
  416 |     /*
      |      
css.cpp:488:1: warning: "/*" within comment [-Wcomment]
  488 | /*
      |  
css.cpp: In function 'void dfs(int, int, int, std::vector<int>&)':
css.cpp:118:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<SelectorElement>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     if (pos == Selector.size()) {
      |         ~~~~^~~~~~~~~~~~~~~~~~
css.cpp: In function 'std::vector<HTMLelement> read_document()':
css.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
css.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%s", tag_start);
      |         ~~~~~^~~~~~~~~~~~~~~~~
css.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |             scanf(" id='%[^']'", name);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
css.cpp:71:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |             scanf(" class='");
      |             ~~~~~^~~~~~~~~~~~
css.cpp:75:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |             scanf("'>");
      |             ~~~~~^~~~~~
css.cpp: In function 'std::vector<SelectorElement> read_selector()':
css.cpp:93:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |             scanf(" %c", &c);
      |             ~~~~~^~~~~~~~~~~
css.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |             scanf(".");
      |             ~~~~~^~~~~
css.cpp: In function 'int main()':
css.cpp:148:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |     scanf("%d\n", &M);
      |     ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10