oj.uz

Submission #784987

# Submission time Handle Problem Language Result Execution time Memory
784987 2023-07-16T20:52:06 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 225 ms 272688 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 320 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 249864 KB Output is correct
2 Correct 160 ms 236324 KB Output is correct
3 Correct 144 ms 196564 KB Output is correct
4 Correct 139 ms 187036 KB Output is correct
5 Correct 225 ms 268588 KB Output is correct
6 Correct 215 ms 272688 KB Output is correct
7 Correct 40 ms 10964 KB Output is correct
8 Correct 192 ms 164960 KB Output is correct
9 Correct 157 ms 139344 KB Output is correct
10 Correct 136 ms 135640 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3664 KB Output is correct
2 Correct 11 ms 3164 KB Output is correct
3 Correct 14 ms 3408 KB Output is correct
4 Correct 10 ms 2824 KB Output is correct
5 Correct 12 ms 3144 KB Output is correct
6 Correct 14 ms 3432 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 320 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 174 ms 249864 KB Output is correct
9 Correct 160 ms 236324 KB Output is correct
10 Correct 144 ms 196564 KB Output is correct
11 Correct 139 ms 187036 KB Output is correct
12 Correct 225 ms 268588 KB Output is correct
13 Correct 215 ms 272688 KB Output is correct
14 Correct 40 ms 10964 KB Output is correct
15 Correct 192 ms 164960 KB Output is correct
16 Correct 157 ms 139344 KB Output is correct
17 Correct 136 ms 135640 KB Output is correct
18 Correct 14 ms 3664 KB Output is correct
19 Correct 11 ms 3164 KB Output is correct
20 Correct 14 ms 3408 KB Output is correct
21 Correct 10 ms 2824 KB Output is correct
22 Correct 12 ms 3144 KB Output is correct
23 Correct 14 ms 3432 KB Output is correct
24 Correct 151 ms 204584 KB Output is correct
25 Correct 165 ms 204676 KB Output is correct
26 Correct 149 ms 202120 KB Output is correct
27 Correct 135 ms 162400 KB Output is correct
28 Correct 93 ms 42464 KB Output is correct
29 Correct 42 ms 10336 KB Output is correct