Submission #745519

#	Time	Username	Problem	Language	Result	Execution time	Memory
745519		lukadupli	CSS (COI14_css)	C++14	20 / 100	5087 ms	262144 KiB

css

#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 (stderr)

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++){
      |                        ~~^~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10