Submission #245539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
245539	2020-07-06T16:56:11 Z	abeker	CSS (COI14_css)	C++17	60 / 100	1278 ms	29752 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;
  vector <Element*> children;
  bool curr, prev;
public:
  Element() {
    curr = prev = false;
  }
  void input(int &n, const function <int(const string&)> &hsh, const function <vector <string>(string, const string&)> &separate) {
    while (n--) {
      string line;
      getline(cin, line);
      vector <string> in_quotes = separate(line, "'");
      if (in_quotes.size() <= 1)
        break;
      Element* child = new Element();
      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 -> input(n, hsh, separate);
    }
  }
  void dfs(const vector <int> &h, const int &type, bool sofar) {
    curr = true;
    for (auto it : h)
      if (!belongs[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(h, 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;
}

Element* root;

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

void SolveSelector() {
  string selector;
  getline(cin, selector);
  vector <string> classifiers = MySeparate(selector, " ");
  string prev = "";
  for (auto it : classifiers) {
    if (it != ">") {
      vector <string> classes = MySeparate(it, ".");
      vector <int> hashes;
      for (auto it : classes)
        hashes.push_back(MyHash(it));
      root -> dfs(hashes, 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:105: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:83: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:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d ", &M);
   ~~~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	7 ms	512 KB	Output isn't correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	2716 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1042 ms	5496 KB	Output isn't correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	357 ms	29436 KB	Output is correct
2	Correct	680 ms	3872 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	380 ms	29356 KB	Output is correct
2	Correct	676 ms	3860 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
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	358 ms	28792 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	484 ms	28536 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	496 ms	29176 KB	Output is correct
2	Correct	953 ms	5716 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1278 ms	29752 KB	Output is correct
2	Correct	684 ms	3872 KB	Output is correct