Submission #784987

#	Time	Username	Problem	Language	Result	Execution time	Memory
784987		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	225 ms	272688 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

int chrToHash[256]{};

int n, m;
vector<string> str;
vector<int> results;

struct TrieNode
{
    int cnt = 0;
    int l = -1, r = -1;
    vector<int> v;
    string* ogString{};
    TrieNode* children[4]{};

    void depthFirstSearch(int& timer);
};

vector<TrieNode*> trieNodes;

void TrieNode::depthFirstSearch(int& timer)
{
    l = timer, timer += cnt;
    for (int i = 0; i < cnt; i++)
        trieNodes.push_back(this);
    for (auto &child : children)
    {
        if (child == nullptr) continue;
        child->depthFirstSearch(timer);
    }
    r = timer;
}

struct Trie
{
    TrieNode *root = new TrieNode;

    void insert(string& s)
    {
        auto curr = root;
        int size = (int)s.size();
        for (int i = 0; i < size; i++)
        {
            int d = chrToHash[s[i]];
            if (curr->children[d] == nullptr)
                curr->children[d] = new TrieNode;
            curr = curr->children[d];
        }
        curr->ogString = &s;
        curr->cnt++;
    }

    TrieNode* getNode(const string& s)
    {
        auto curr = root;
        int size = (int)s.size();
        for (int i = 0; i < size; i++)
        {
            int d = chrToHash[s[i]];
            if (curr->children[d] == nullptr)
                return nullptr;
            curr = curr->children[d];
        }
        return curr;
    }

    void process()
    {
        int timer = 0;
        trieNodes.reserve(n);
        root->depthFirstSearch(timer);
    }
} trie;

struct Eirt
{
    TrieNode *root = new TrieNode;

    void insert(string& s, const int& index)
    {
        auto curr = root;
        curr->v.push_back(index);
        int size = (int)s.size();
        for (int i = size - 1; i >= 0; i--)
        {
            int d = chrToHash[s[i]];
            if (curr->children[d] == nullptr)
                curr->children[d] = new TrieNode;
            curr = curr->children[d];
            curr->v.push_back(index);
        }
        curr->ogString = &s;
    }

    TrieNode* getNode(const string& s)
    {
        auto curr = root;
        int size = (int)s.size();
        for (int i = size - 1; i >= 0; i--)
        {
            int d = chrToHash[s[i]];
            if (curr->children[d] == nullptr)
                return nullptr;
            curr = curr->children[d];
        }
        return curr;
    }
} eirt;

int main()
{
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);

    ios::sync_with_stdio(false);

    chrToHash['A'] = 0;
    chrToHash['C'] = 1;
    chrToHash['G'] = 2;
    chrToHash['U'] = 3;

    cin >> n >> m;
    str.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> str[i];
        trie.insert(str[i]);
    }

    trie.process();

    for (int i = 0; i < n; i++)
        eirt.insert(*trieNodes[i]->ogString, i);

    results.resize(m);
    string pref, suff;
    for (int q = 0; q < m; q++)
    {
        cin >> pref >> suff;
        auto itr = trie.getNode(pref);
        auto jtr = eirt.getNode(suff);
        if (itr == nullptr || jtr == nullptr)
        {
            results[q] = 0;
            continue;
        }
        auto l = lower_bound(jtr->v.begin(), jtr->v.end(), itr->l);
        auto r = lower_bound(jtr->v.begin(), jtr->v.end(), itr->r);
        results[q] = r - l;
    }

    for (auto &result : results)
        cout << result << '\n';
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::insert(std::string&)':
selling_rna.cpp:47:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   47 |             int d = chrToHash[s[i]];
      |                                   ^
selling_rna.cpp: In member function 'TrieNode* Trie::getNode(const string&)':
selling_rna.cpp:62:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |             int d = chrToHash[s[i]];
      |                                   ^
selling_rna.cpp: In member function 'void Eirt::insert(std::string&, const int&)':
selling_rna.cpp:89:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |             int d = chrToHash[s[i]];
      |                                   ^
selling_rna.cpp: In member function 'TrieNode* Eirt::getNode(const string&)':
selling_rna.cpp:104:35: warning: array subscript has type 'char' [-Wchar-subscripts]
  104 |             int d = chrToHash[s[i]];
      |                                   ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40