Submission #245555

#	Time	Username	Problem	Language	Result	Execution time	Memory
245555		abeker	CSS (COI14_css)	C++17	100 / 100	2463 ms	24872 KiB

css

#include <bits/stdc++.h>
using namespace std;

const int BASE = 3137;
const int MOD = 1e9 + 7;

class Element {
  string name;
  unordered_map <int, bool> belongs;
  function <int(const string&)> hsh;
  vector <Element*> children;
  bool curr, prev;
public:
  Element(function <int(const string&)> _hsh) {
    hsh = _hsh;
    curr = prev = false;
  }
  void parse(int &n, const function <string()> &input, const function <vector <string>(string, const string&)> &separate) {
    while (n--) {
      vector <string> in_quotes = separate(input(), "'");
      if (in_quotes.size() <= 1)
        break;
      Element* child = new Element(hsh);
      children.push_back(child);
      child -> name = in_quotes[1];
      vector <string> classes = separate(in_quotes[3], " ");
      for (auto it : classes)
        child -> belongs[hsh(it)] = true;
      child -> parse(n, input, separate);
    }
  }
  void dfs(const vector <string> &classes, const int &type, bool sofar) {
    curr = true;
    for (auto it : classes)
      if (!belongs[hsh(it)]) {
        curr = false;
        break;
      }
    if (type)
      curr &= sofar;
    if (type == 1)
      sofar |= prev;
    else if (type == 2)
      sofar = prev;
    for (auto it : children)
      it -> dfs(classes, type, sofar);
    swap(curr, prev);
  }
  void getCorr(vector <string> &v) const {
    if (prev)
      v.push_back(name);
    for (auto it : children)
      it -> getCorr(v);
  }
};

int MyHash(const string &s) {
  int res = 0;
  for (auto it : s)
    res = ((long long)BASE * res + it) % MOD;
  return res;
}

vector <string> MySeparate(string s, const string &delim) {
  s += delim;
  vector <string> res;
  size_t pos = 0;
  while (1) {
    size_t nxt = s.find(delim, pos);
    if (nxt == string::npos)
      break;
    if (pos < nxt)
      res.push_back(s.substr(pos, nxt - pos));
    pos = nxt + 1;
  }
  return res;
}

string MyInput() {
  string s;
  getline(cin, s);
  while (!s.empty() && s.back() != '>' && !islower(s.back()))
    s.pop_back();
  return s;
}

Element* root;

void load() {
  int N;
  scanf("%d ", &N);
  root = new Element(MyHash);
  root -> parse(N, MyInput, MySeparate);
}

void SolveSelector() {
  string selector = MyInput();
  vector <string> classifiers = MySeparate(selector, " ");
  string prev = "";
  for (auto it : classifiers) {
    if (it != ">") 
      root -> dfs(MySeparate(it, "."), prev.empty() ? 0 : (prev == ">" ? 2 : 1), false);
    prev = it;
  }
  vector <string> ans;
  root -> getCorr(ans);
  printf("%d", ans.size());
  for (auto it : ans)
    printf(" %s", it.c_str());
  puts("");
}

void solve() {
  int M;
  scanf("%d ", &M);
  while (M--) 
    SolveSelector();
}

int main() {
  load();
  solve();
  return 0;
}

Compilation message (stderr)

css.cpp: In function 'void SolveSelector()':
css.cpp:107:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::__cxx11::basic_string<char> >::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d", ans.size());
                ~~~~~~~~~~^
css.cpp: In function 'void load()':
css.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d ", &N);
   ~~~~~^~~~~~~~~~~
css.cpp: In function 'void solve()':
css.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d ", &M);
   ~~~~~^~~~~~~~~~~

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