| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1016450 |
2024-07-08T05:29:44 Z |
dondurma |
CSS (COI14_css) |
C++17 |
|
764 ms |
65804 KB |
#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
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()) {
| ~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2504 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
50660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
2528 KB |
Execution killed with signal 7 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
65752 KB |
Output is correct |
| 2 |
Correct |
497 ms |
51140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
185 ms |
65756 KB |
Output is correct |
| 2 |
Correct |
502 ms |
51112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
49496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
83 ms |
32728 KB |
Execution killed with signal 7 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
32736 KB |
Execution killed with signal 7 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
65748 KB |
Output is correct |
| 2 |
Correct |
764 ms |
51676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
455 ms |
65804 KB |
Output is correct |
| 2 |
Correct |
431 ms |
51160 KB |
Output is correct |
