Submission #1016194

#TimeUsernameProblemLanguageResultExecution timeMemory
1016194dondurmaCSS (COI14_css)C++17
10 / 100
1050 ms66008 KiB
#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(string str) { int hash = 0; for(auto x : str) hash = hash * 71 + x - 'a' + 1; classes.insert(hash); } }; struct SelectorElement { int type; vector<int> classes; SelectorElement(int type): type(type) {} void add_class(string str) { int hash = 0; for(auto x : str) hash = hash * 71 + x - '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() { 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) { string s; cin >> s; if(s[1] == '/') { ancestors.pop(); } else { cin >> s; char name[31]; int num = 0; for (int j = 4;j < s.size() - 1;j++) { name[num++] = s[j]; } tree.push_back(HTMLelement(name)); tree[ancestors.top()].add_child(tree.size() - 1); ancestors.push(tree.size() - 1); string class_name = ""; int j = 7; while(1) { cin >> s; class_name = ""; bool f = 0; num = 0; for (;j < s.size();j++) { if (s[j] == 39) { f = 1; break; } class_name += s[j]; } j = 0; tree.back().add_class(class_name); if (f) break; } } } return tree; } vector<SelectorElement> read_selector(string s) { vector<SelectorElement> sel; int j = 0; while(j < s.size()) { char c = s[j]; if(c == ' ') { j++; continue; } if(c == '>') { sel.push_back(SelectorElement(0)); j += 2; } else sel.push_back(SelectorElement(1)); sel.push_back(SelectorElement(2)); string class_name = ""; while(1) { j++; c = s[j]; if (c == '.') { if (!class_name.empty()) sel.back().add_class(class_name); class_name = ""; continue; } if (c == ' ') { sel.back().add_class(class_name); break; } class_name += c; if (j == s.size() - 1) { sel.back().add_class(class_name); break; } } if (j == s.size() - 1) break; } 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(); int M; scanf("%d\n", &M); // fflush(stdin); string s; // getline(cin, s); for(int i = 0; i < M; ++i) { getline(cin, s); Selector = read_selector(s); memset(visited, 0, sizeof visited); vector<int> ans; dfs(0, 0, 0, ans); cout << (int)ans.size() << " "; sort(ans.begin(), ans.end()); for(auto id : ans) cout << DocumentTree[id].id << " "; cout << endl; } return 0; }

Compilation message (stderr)

css.cpp: In function 'std::vector<HTMLelement> read_document()':
css.cpp:63:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for (int j = 4;j < s.size() - 1;j++) {
      |                            ~~^~~~~~~~~~~~~~
css.cpp:78:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                 for (;j < s.size();j++) {
      |                       ~~^~~~~~~~~~
css.cpp: In function 'std::vector<SelectorElement> read_selector(std::string)':
css.cpp:99:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     while(j < s.size()) {
      |           ~~^~~~~~~~~~
css.cpp:127:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |             if (j == s.size() - 1) {
      |                 ~~^~~~~~~~~~~~~~~
css.cpp:133:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         if (j == s.size() - 1) break;
      |             ~~^~~~~~~~~~~~~~~
css.cpp: In function 'void dfs(int, int, int, std::vector<int>&)':
css.cpp:146:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<SelectorElement>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     if(pos == Selector.size()) {
      |        ~~~~^~~~~~~~~~~~~~~~~~
css.cpp: In function 'std::vector<HTMLelement> read_document()':
css.cpp:47:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     int N; scanf("%d", &N);
      |            ~~~~~^~~~~~~~~~
css.cpp: In function 'int main()':
css.cpp:171:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |     int M; scanf("%d\n", &M);
      |            ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...