| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 745519 |
2023-05-20T09:30:14 Z |
lukadupli |
CSS (COI14_css) |
C++14 |
|
5000 ms |
262144 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 5, MAXS = 1e3 + 5;
int cnt = 0, cls_cnt = 0;
map<string, int> enc, cls_enc;
vector<string> dcd;
set<int> klase[MAXN];
vector<int> anc[MAXN];
int par[MAXN];
void getint(int &x){
string s;
getline(cin, s);
x = stoi(s);
}
vector<int> stck;
void parse(string& v){
if(v == "</div>"){
stck.pop_back();
return;
}
int ps = v.find("'"), ps2 = v.find("'", ps + 1);
string name;
for(int i = ps + 1; i < ps2; i++) name.push_back(v[i]);
enc[name] = ++cnt;
dcd.push_back(name);
for(int e : stck) anc[cnt].push_back(e);
if(!stck.empty()) par[cnt] = stck.back();
stck.push_back(cnt);
ps = v.find("'", ps2 + 1);
string cls;
for(int i = ps + 1; i < v.size(); i++){
if(v[i] == ' ' || v[i] == '\''){
if(cls_enc.find(cls) != cls_enc.end()) klase[cnt].insert(cls_enc[cls]);
else{
cls_enc[cls] = ++cls_cnt;
klase[cnt].insert(cls_cnt);
}
cls.clear();
if(v[i] == '\'') break;
}
else cls.push_back(v[i]);
}
}
struct Classifier{
vector<int> kls;
Classifier(const string& s){
string v = s;
v.push_back('.');
string cls;
for(int i = 1; i < v.size(); i++){
if(v[i] == '.'){
if(cls_enc.find(cls) != cls_enc.end()) kls.push_back(cls_enc[cls]);
else{
cls_enc[cls] = ++cls_cnt;
kls.push_back(cls_cnt);
}
cls.clear();
}
else cls.push_back(v[i]);
}
}
bool belongs(int elem){
for(int e : kls){
if(klase[elem].find(e) == klase[elem].end()) return 0;
}
return 1;
}
void print(){
cout << "Classifier: ";
for(int e : kls) cout << e << ' ';
cout << '\n';
}
};
vector<pair<Classifier, bool>> selector;
void parse_selector(string v){
selector.clear();
v.push_back(' ');
string cfier;
for(int i = 0; i < v.size(); i++){
if(v[i] == ' '){
selector.push_back({Classifier(cfier), 0});
if(i < v.size() - 1 && v[i + 1] == '>'){
selector.back().second = 1;
i += 2;
}
cfier.clear();
}
else cfier.push_back(v[i]);
}
}
int memo[MAXN][MAXS];
bool corresponds(int elem, int pos){
if(memo[elem][pos] != -1) return memo[elem][pos];
if(!selector[pos].first.belongs(elem)) return memo[elem][pos] = 0;
if(pos == 0) return memo[elem][pos] = 1;
if(selector[pos - 1].second) return memo[elem][pos] = corresponds(par[elem], pos - 1);
memo[elem][pos] = 0;
for(int e : anc[elem]) memo[elem][pos] |= corresponds(e, pos - 1);
return memo[elem][pos];
}
void print_elems(){
for(int i = 1; i < dcd.size(); i++){
cout << "elem: " << dcd[i] << ":\n";
cout << " parent: " << dcd[par[i]] << '\n';
cout << " ancestors: "; for(int e : anc[i]) cout << dcd[e] << ' ';
cout << '\n';
cout << " klase: "; for(int e : klase[i]) cout << e << ' ';
cout << "\n\n";
}
}
void print_selector(){
for(auto c : selector){
c.first.print();
cout << (c.second ? "flag" : "no flag") << '\n';
}
cout << '\n';
}
int main()
{
dcd.push_back("");
int n;
getint(n);
for(int i = 0; i < n; i++){
string s;
getline(cin, s);
parse(s);
}
//print_elems();
getint(n);
vector<int> ok;
for(int i = 0; i < n; i++){
string s;
getline(cin, s);
parse_selector(s);
//print_selector();
ok.clear();
for(int j = 0; j < dcd.size(); j++){
for(int k = 0; k < selector.size(); k++) memo[j][k] = -1;
}
for(int j = 1; j < dcd.size(); j++){
if(corresponds(j, selector.size() - 1)) ok.push_back(j);
}
cout << ok.size() << ' ';
for(int e : ok) cout << dcd[e] << ' ';
cout << '\n';
}
return 0;
}
Compilation message
css.cpp: In function 'void parse(std::string&)':
css.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = ps + 1; i < v.size(); i++){
| ~~^~~~~~~~~~
css.cpp: In constructor 'Classifier::Classifier(const string&)':
css.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i = 1; i < v.size(); i++){
| ~~^~~~~~~~~~
css.cpp: In function 'void parse_selector(std::string)':
css.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
css.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if(i < v.size() - 1 && v[i + 1] == '>'){
| ~~^~~~~~~~~~~~~~
css.cpp: In function 'bool corresponds(int, int)':
css.cpp:117:67: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
117 | if(!selector[pos].first.belongs(elem)) return memo[elem][pos] = 0;
| ~~~~~~~~~~~~~~~~^~~
css.cpp:118:41: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
118 | if(pos == 0) return memo[elem][pos] = 1;
| ~~~~~~~~~~~~~~~~^~~
css.cpp:120:57: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
120 | if(selector[pos - 1].second) return memo[elem][pos] = corresponds(par[elem], pos - 1);
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
css.cpp: In function 'void print_elems()':
css.cpp:129:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int i = 1; i < dcd.size(); i++){
| ~~^~~~~~~~~~~~
css.cpp: In function 'int main()':
css.cpp:171:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for(int j = 0; j < dcd.size(); j++){
| ~~^~~~~~~~~~~~
css.cpp:172:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<Classifier, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int k = 0; k < selector.size(); k++) memo[j][k] = -1;
| ~~^~~~~~~~~~~~~~~~~
css.cpp:174:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for(int j = 1; j < dcd.size(); j++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7636 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
34508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
362 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
575 ms |
74308 KB |
Output is correct |
| 2 |
Execution timed out |
5062 ms |
55492 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
794 ms |
73808 KB |
Output is correct |
| 2 |
Execution timed out |
5042 ms |
55520 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
525 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
557 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
911 ms |
74016 KB |
Output is correct |
| 2 |
Execution timed out |
5055 ms |
83448 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2460 ms |
73952 KB |
Output is correct |
| 2 |
Execution timed out |
5087 ms |
55632 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
