oj.uz

Submission #548648

# Submission time Handle Problem Language Result Execution time Memory
548648 2022-04-14T06:50:59 Z colossal_pepe Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 139908 KB 
#include <iostream>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <algorithm>
using namespace std;

unordered_map<char, int> id;

struct Node {
    int children[4][4];
    int cnt = 0;
    Node() {
        memset(children, -1, sizeof(children));
        cnt = 0;
    }
};

struct Trie {
    vector<Node> trie;
    Trie() {
        trie = {Node()};
    }
    void insert(const string& s) {
        int node = 0;
        trie[node].cnt++;
        int sz = s.size();
        for (int i = 0; i < sz; i++) {
            int x = id[s[i]], y = id[s[sz - 1 - i]];
            if (trie[node].children[x][y] == -1) {
                trie[node].children[x][y] = trie.size();
                trie.push_back(Node());
            }
            node = trie[node].children[x][y];
            trie[node].cnt++;
        }
    }
    int query(int node, int i, const string& pref, const string& suf) {
        int ans = 0;
        if (i < pref.size() and i < suf.size()) {
            int x = id[pref[i]], y = id[suf[i]];
            if (trie[node].children[x][y] != -1) ans = query(trie[node].children[x][y], i + 1, pref, suf);
        } else if (i < pref.size()) {
            int x = id[pref[i]];
            for (int y = 0; y < 4; y++) {
                if (trie[node].children[x][y] != -1) ans += query(trie[node].children[x][y], i + 1, pref, suf);
            }
        } else if (i < suf.size()) {
            int y = id[suf[i]];
            for (int x = 0; x < 4; x++) {
                if (trie[node].children[x][y] != -1) ans += query(trie[node].children[x][y], i + 1, pref, suf);
            }
        } else ans = trie[node].cnt;
        return ans;
    }
};

int n, q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    id['A'] = 0, id['G'] = 1, id['C'] = 2, id['U'] = 3;
    Trie trie = Trie();
    cin >> n >> q;
    while (n--) {
        string s;
        cin >> s;
        trie.insert(s);
    }
    while (q--) {
        string pref, suf;
        cin >> pref >> suf;
        reverse(suf.begin(), suf.end());
        cout << trie.query(0, 0, pref, suf) << '\n';
    }
    return 0;
}

Compilation message

selling_rna.cpp: In member function 'int Trie::query(int, int, const string&, const string&)':
selling_rna.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if (i < pref.size() and i < suf.size()) {
      |             ~~^~~~~~~~~~~~~
selling_rna.cpp:40:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if (i < pref.size() and i < suf.size()) {
      |                                 ~~^~~~~~~~~~~~
selling_rna.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         } else if (i < pref.size()) {
      |                    ~~^~~~~~~~~~~~~
selling_rna.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         } else if (i < suf.size()) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1577 ms 139908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 564 KB Output is correct
2 Correct 34 ms 1220 KB Output is correct
3 Correct 28 ms 1132 KB Output is correct
4 Correct 15 ms 844 KB Output is correct
5 Correct 36 ms 1128 KB Output is correct
6 Correct 24 ms 1088 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Execution timed out 1577 ms 139908 KB Time limit exceeded
9 Halted 0 ms 0 KB -