Submission #691695

#	Time	Username	Problem	Language	Result	Execution time	Memory
691695		danikoynov	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	268 ms	454408 KiB

selling_rna

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10, alphabet = 26;

int n, m;
string rna[maxn];

struct query
{
    string p, q;
}ask[maxn];

void input()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> rna[i];
    for (int i = 1; i <= m; i ++)
        cin >> ask[i].p >> ask[i].q;
}

struct sub_trie
{
    sub_trie *child[alphabet];
    int cnt;

    sub_trie()
    {
        for (int i = 0; i < alphabet; i ++)
            child[i] = NULL;
        cnt = 0;
    }

    int add(string &word, int pos)
    {
        cnt ++;
        if (pos == word.size())
            return 0;

        int go = word[pos] - 'A', to_add = 0;
        if (child[go] == NULL)
        {
            to_add = 0;
            child[go] = new sub_trie();
        }

        return to_add + child[go] -> add(word, pos + 1);
    }

    int find_suffix(string &word, int pos)
    {
        if (pos == word.size())
            return cnt;

        int go = word[pos] - 'A';
        if (child[go] == NULL)
            return 0;

        return child[go] -> find_suffix(word, pos + 1);
    }
};

void merge_sub_trie(sub_trie *&prim, sub_trie *sec)
{
    if (sec == NULL)
        return;

    if (prim == NULL)
    {
        prim = sec;
        return;
    }

    prim -> cnt += sec -> cnt;
    for (int i = 0; i < alphabet; i ++)
    {
        if (sec -> child[i] != NULL)
            merge_sub_trie(prim -> child[i],  sec -> child[i]);
    }
}

struct trie
{
    trie *child[alphabet];
    sub_trie *suffix;
    int suffix_len;
    vector < pair < string, int > > tasks;

    trie()
    {
        for (int i = 0; i < alphabet; i ++)
            child[i] = NULL;
        suffix_len = 0;
        suffix = new sub_trie();
    }

    void add(string &word, int pos)
    {
        if (pos == word.size())
        {
            string temp = word;
            reverse(temp.begin(), temp.end());
            suffix_len += suffix -> add(temp, 0);
            return;
        }

        int go = word[pos] - 'A';
        if (child[go] == NULL)
            child[go] = new trie();

        child[go] -> add(word, pos + 1);
    }

    void push_query(string &word, int pos, string &suff, int idx)
    {
        if (pos == word.size())
        {
            tasks.push_back({suff, idx});
            return;
        }

        int go = word[pos] - 'A';
        if (child[go] == NULL)
            return;

        child[go] -> push_query(word, pos + 1, suff, idx);
    }
};

trie *root = new trie();
void build_trie()
{
    for (int i = 1; i <= n; i ++)
    {
        root -> add(rna[i], 0);
    }
}

void insert_queries()
{
    for (int i = 1; i <= m; i ++)
        root -> push_query(ask[i].p, 0, ask[i].q, i);
}

int ans[maxn];
void dfs(trie *root)
{
    int mx = -1, max_len = -1;
    for (int i = 0; i < alphabet; i ++)
    {
        if (root -> child[i] != NULL)
        {
            dfs(root -> child[i]);
            if (root -> child[i] -> suffix_len > max_len)
            {
                max_len = root -> child[i] -> suffix_len;
                mx = i;
            }
        }
    }

    if (mx != - 1)
    {
        swap(root -> suffix, root -> child[mx] -> suffix);
    }

    for (int i = 0; i < alphabet; i ++)
    {
        if (root -> child[i] == NULL ||
            i == mx)
            continue;

        merge_sub_trie(root -> suffix, root -> child[i] -> suffix);
    }

    for (pair < string, int > cur : root -> tasks)
    {
        ans[cur.second] = root -> suffix -> find_suffix(cur.first, 0);
    }
}
void solve_queries()
{
    dfs(root);

    for (int i = 1; i <= m; i ++)
        cout << ans[i] << endl;
}

void solve()
{
    input();
    build_trie();
    insert_queries();
    solve_queries();
}

int main()
{
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'int sub_trie::add(std::string&, int)':
selling_rna.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if (pos == word.size())
      |             ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In member function 'int sub_trie::find_suffix(std::string&, int)':
selling_rna.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         if (pos == word.size())
      |             ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In member function 'void trie::add(std::string&, int)':
selling_rna.cpp:110:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         if (pos == word.size())
      |             ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In member function 'void trie::push_query(std::string&, int, std::string&, int)':
selling_rna.cpp:127:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         if (pos == word.size())
      |             ~~~~^~~~~~~~~~~~~~

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