oj.uz

답안 #245539

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 512 KB Output isn't correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 2716 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1042 ms 5496 KB Output isn't correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 512 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 358 ms 28792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 484 ms 28536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1278 ms 29752 KB Output is correct
2 Correct 684 ms 3872 KB Output is correct