Submission #245555

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
245555	2020-07-06T18:07:23 Z	abeker	CSS (COI14_css)	C++17	100 / 100	2463 ms	24872 KB

#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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	512 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	2580 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1068 ms	5096 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	416 ms	23288 KB	Output is correct
2	Correct	969 ms	3444 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	444 ms	23108 KB	Output is correct
2	Correct	964 ms	3480 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	512 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	391 ms	22776 KB	Output is correct
2	Correct	1359 ms	5076 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	635 ms	23692 KB	Output is correct
2	Correct	944 ms	3724 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	800 ms	23960 KB	Output is correct
2	Correct	1357 ms	4904 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2463 ms	24872 KB	Output is correct
2	Correct	934 ms	3476 KB	Output is correct