Submission #1016450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016450		dondurma	CSS (COI14_css)	C++17	60 / 100	764 ms	65804 KiB

css

#include <bits/stdc++.h>

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;
    }
};

int input(string s) {
    int x = 0;
    for (auto c : s) x = x * 10 + c - '0';
    return x;
}

vector<HTMLelement> read_document() {
    string s;
    getline(cin, s);
    int N = input(s);

    stack<int> ancestors;

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

    for(int i = 0; i < N; ++i) {
        getline(cin, s);
        if(s.find("</div>") != string::npos) {
            ancestors.pop();
        } else {
            char name[31];
            memset(name, 0, sizeof name);
            int idp = s.find("id='") + 4;
            for (int j = 0;;j++) {
                if (j + idp >= s.size()) break;
                if (s[j + idp] == 39) break;
                name[j] = s[j + idp];
            }

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

            int j = s.find("class='") + 7, num = 0;
            if (s.find("class='") == string::npos) continue;
            while(true) {
                char class_name[31];
                memset(class_name, 0, sizeof class_name);
                bool f = 0;
                num = 0;
                while (true) {
                    // if (j >= s.size()) assert(0);
                    if (s[j] == ' ') {
                        j++;
                        break;
                    }
                    if (s[j] == 39) {
                        f = 1;
                        break;
                    }
                    // if (num == 31) assert(0);
                    class_name[num++] = s[j]; 
                    j++;
                }
                tree.back().add_class(class_name);
                if (f) break;
            }
        }
    }

    return tree;
}

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

    string s; 
    getline(cin, s);
    
    int num = 0, j = 0;
    while (j < s.size()) {
        if (s[j] == '>') {
            sel.push_back(SelectorElement(0));
            j += 2;
        } else {
            if (j == 0 || (s[j - 1] == ' ' && s[j - 2] != '>')) sel.push_back(SelectorElement(1));
            sel.push_back(SelectorElement(2));
            num = 0;
            char class_name[21];
            memset(class_name, 0, sizeof class_name);
            j++;
            while (j < s.size()) {
                if (s[j] == ' ') {
                    break;
                }
                // if (num == 21) {
                //     assert(0);
                // }
                class_name[num++] = s[j];
                if (j == s.size() - 1 || s[j + 1] == '.') break;
                j++;
            }
            sel.back().add_class(class_name);
            j++;
        }
    }

    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() {
    
    DocumentTree = read_document();

    string s;
    getline(cin, s);
    int M = input(s);
    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;

}

Compilation message (stderr)

css.cpp: In function 'std::vector<HTMLelement> read_document()':
css.cpp:74:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                 if (j + idp >= s.size()) break;
      |                     ~~~~~~~~^~~~~~~~~~~
css.cpp: In function 'std::vector<SelectorElement> read_selector()':
css.cpp:120:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     while (j < s.size()) {
      |            ~~^~~~~~~~~~
css.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |             while (j < s.size()) {
      |                    ~~^~~~~~~~~~
css.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |                 if (j == s.size() - 1 || s[j + 1] == '.') break;
      |                     ~~^~~~~~~~~~~~~~~
css.cpp: In function 'void dfs(int, int, int, std::vector<int>&)':
css.cpp:158:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<SelectorElement>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     if(pos == Selector.size()) {
      |        ~~~~^~~~~~~~~~~~~~~~~~

• 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