Submission #548648

#	Time	Username	Problem	Language	Result	Execution time	Memory
548648		colossal_pepe	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1577 ms	139908 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40