| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 962044 |
2024-04-13T05:40:42 Z |
riariti |
CSS (COI14_css) |
C++17 |
|
1449 ms |
69460 KB |
#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
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);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
49468 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
50668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1449 ms |
51804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
69416 KB |
Output is correct |
| 2 |
Correct |
725 ms |
51372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
183 ms |
69316 KB |
Output is correct |
| 2 |
Correct |
685 ms |
51396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
49504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
69100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
189 ms |
69340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
272 ms |
69404 KB |
Output is correct |
| 2 |
Correct |
1101 ms |
51820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
617 ms |
69460 KB |
Output is correct |
| 2 |
Correct |
624 ms |
51420 KB |
Output is correct |
