| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1016188 |
2024-07-07T13:31:48 Z |
dondurma |
CSS (COI14_css) |
C++17 |
|
1083 ms |
69400 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(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; cin >> 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; cin >> 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
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()) {
| ~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
49496 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
50884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1083 ms |
51836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
186 ms |
69400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
69336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
49496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
186 ms |
69080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
244 ms |
69336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
225 ms |
69336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
480 ms |
69360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
