oj.uz

Submission #784878

# Submission time Handle Problem Language Result Execution time Memory
784878 2023-07-16T16:53:01 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 222 ms 272532 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 = INT_MAX, r = INT_MIN;
    vector<int> v;
    string* ogString{};
    TrieNode* children[4]{};
    TrieNode* parent{};

    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);
        l = min(child->l, l);
        r = max(child->r, r);
    }
    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;
        root->depthFirstSearch(timer);
    }
} trie;

struct Eirt
{
    TrieNode *root = new TrieNode;

    void insert(string& s, const int& index)
    {
        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)
            {
                curr->children[d] = new TrieNode;
                curr->children[d]->parent = curr;
            }
            curr = curr->children[d];
        }
        curr->ogString = &s;
        curr->v.push_back(index);
        while (curr != root)
        {
            curr = curr->parent;
            curr->v.push_back(index);
        }
    }

    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:50:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |             int d = chrToHash[s[i]];
      |                                   ^
selling_rna.cpp: In member function 'TrieNode* Trie::getNode(const string&)':
selling_rna.cpp:65:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   65 |             int d = chrToHash[s[i]];
      |                                   ^
selling_rna.cpp: In member function 'void Eirt::insert(std::string&, const int&)':
selling_rna.cpp:90:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   90 |             int d = chrToHash[s[i]];
      |                                   ^
selling_rna.cpp: In member function 'TrieNode* Eirt::getNode(const string&)':
selling_rna.cpp:113:35: warning: array subscript has type 'char' [-Wchar-subscripts]
  113 |             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 0 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 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 184 ms 249448 KB Output is correct
2 Correct 188 ms 236124 KB Output is correct
3 Correct 161 ms 196420 KB Output is correct
4 Correct 170 ms 187196 KB Output is correct
5 Correct 215 ms 268568 KB Output is correct
6 Correct 222 ms 272532 KB Output is correct
7 Correct 48 ms 10848 KB Output is correct
8 Correct 194 ms 164868 KB Output is correct
9 Correct 165 ms 139172 KB Output is correct
10 Correct 125 ms 135372 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3796 KB Output is correct
2 Correct 11 ms 2856 KB Output is correct
3 Correct 13 ms 3276 KB Output is correct
4 Correct 10 ms 2556 KB Output is correct
5 Correct 12 ms 2900 KB Output is correct
6 Correct 14 ms 3148 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 0 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 184 ms 249448 KB Output is correct
9 Correct 188 ms 236124 KB Output is correct
10 Correct 161 ms 196420 KB Output is correct
11 Correct 170 ms 187196 KB Output is correct
12 Correct 215 ms 268568 KB Output is correct
13 Correct 222 ms 272532 KB Output is correct
14 Correct 48 ms 10848 KB Output is correct
15 Correct 194 ms 164868 KB Output is correct
16 Correct 165 ms 139172 KB Output is correct
17 Correct 125 ms 135372 KB Output is correct
18 Correct 14 ms 3796 KB Output is correct
19 Correct 11 ms 2856 KB Output is correct
20 Correct 13 ms 3276 KB Output is correct
21 Correct 10 ms 2556 KB Output is correct
22 Correct 12 ms 2900 KB Output is correct
23 Correct 14 ms 3148 KB Output is correct
24 Correct 160 ms 204448 KB Output is correct
25 Correct 165 ms 204684 KB Output is correct
26 Correct 157 ms 201952 KB Output is correct
27 Correct 145 ms 162404 KB Output is correct
28 Correct 94 ms 42332 KB Output is correct
29 Correct 45 ms 10440 KB Output is correct