Submission #848604

#	Time	Username	Problem	Language	Result	Execution time	Memory
848604		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	85 ms	136712 KiB

selling_rna

#include <bits/stdc++.h>
#define fi first
#define se second

#define task "RNA"

using namespace std;

const int N = 1e5;

int n, q, ans[2 * N];
string k[2 * N];

struct Trie
{
    struct Node
    {
        int child[4];
        int cnt;
    } nodes[4 * N];
    pair<int, vector<int>> endStr[4 * N];
    vector<pair<string, int>> ask[4 * N];

    int cur;
    Trie() : cur(0)
    {
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        nodes[0].cnt = 0;
    };

    int new_node()
    {
        cur++;
        nodes[cur].child[0] = nodes[cur].child[1] = nodes[cur].child[2] = nodes[cur].child[3] = -1;
        nodes[cur].cnt = 0;
        return cur;
    }

    int Pos(char k)
    {
        if (k == 'A')
            return 0;
        if (k == 'U')
            return 1;
        if (k == 'C')
            return 3;
        return 2;
    }

    void add_string(string &s, int posi)
    {
        int pos = 0, dem = 0;
        for (int i = 0; i < s.size(); i++)
        {
            int c = Pos(s[i]);
            if (nodes[pos].child[c] == -1)
                nodes[pos].child[c] = new_node();
            pos = nodes[pos].child[c];
            nodes[pos].cnt++;
            dem++;
        }
        endStr[pos].se.push_back(posi);
        endStr[pos].fi += dem;
    }

    void find_string(string &s, string tmp, int l)
    {
        int pos = 0;
        for (int i = 0; i < s.size(); i++)
        {
            int c = Pos(s[i]);
            if (nodes[pos].child[c] == -1)
                return;
            pos = nodes[pos].child[c];
        }
        ask[pos].push_back({tmp, l});
    }

    int find_string1(string &s)
    {
        int pos = 0;
        for (int i = 0; i < s.size(); i++)
        {
            int c = Pos(s[i]);
            if (nodes[pos].child[c] == -1)
                return 0;
            pos = nodes[pos].child[c];
        }
        return nodes[pos].cnt;
    }

    bool delStr(int pos, string &s, int i)
    {
        if (i != (int)s.size())
        {
            int c = Pos(s[i]);
            bool isChildDeleted = delStr(nodes[pos].child[c], s, i + 1);
            if (isChildDeleted)
                nodes[pos].child[c] = -1;
        }

        if (pos != 0)
        {
            nodes[pos].cnt--;
            if (nodes[pos].cnt == 0)
                return true;
        }
        return false;
    }
} trie[2];

int dem = 0;
int In[2 * N], Out[2 * N], pos[2 * N];
int sz[2 * N];

void dfs(int u)
{
    In[u] = ++dem;
    pos[dem] = u;
    sz[u] = trie[0].endStr[u].fi;
    for (int i = 0; i <= 3; i++)
    {
        if (trie[0].nodes[u].child[i] == -1)
            continue;
        int x = trie[0].nodes[u].child[i];
        // cout << u << x << '\n';
        dfs(x);
        sz[u] += sz[x];
    }
    Out[u] = dem;
}

void solve(int u)
{
    for (auto i : trie[0].ask[u])
        ans[i.se] = trie[1].find_string1(i.fi);
}

void dfs_solve(int u)
{
    pair<int, int> big = {0, 0};
    for (int i = 0; i <= 3; i++)
    {
        if (trie[0].nodes[u].child[i] == -1)
            continue;
        int x = trie[0].nodes[u].child[i];
        if (big.fi < sz[x])
            big = {sz[x], x};
    }
    for (int i = 0; i <= 3; i++)
    {
        if (trie[0].nodes[u].child[i] == -1)
            continue;
        int x = trie[0].nodes[u].child[i];
        if (x != big.se)
        {
            dfs_solve(x);
            for (int j = In[x]; j <= Out[x]; j++)
            {
                for (auto l : trie[0].endStr[pos[j]].se)
                    trie[1].delStr(0, k[l], 0);
            }
        }
    }
    if (big.se)
        dfs_solve(big.se);
    for (int i = 0; i <= 3; i++)
    {
        if (trie[0].nodes[u].child[i] == -1)
            continue;
        int x = trie[0].nodes[u].child[i];
        if (x != big.se)
        {
            for (int j = In[x]; j <= Out[x]; j++)
            {
                for (auto l : trie[0].endStr[pos[j]].se)
                    trie[1].add_string(k[l], l);
            }
        }
    }
    for (auto l : trie[0].endStr[u].se)
        trie[1].add_string(k[l], l);
    solve(u);
    return;
}

int main()
{
    // freopen(task ".inp", "r", stdin);
    // freopen(task ".out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> q;

    for (int i = 1; i <= n; i++)
    {
        cin >> k[i];
        trie[0].add_string(k[i], i);
        reverse(k[i].begin(), k[i].end());
    }

    dfs(0);

    for (int i = 1; i <= q; i++)
    {
        string u, v;
        cin >> u >> v;
        reverse(v.begin(), v.end());
        trie[0].find_string(u, v, i);
    }

    dfs_solve(0);

    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::add_string(std::string&, int)':
selling_rna.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int i = 0; i < s.size(); i++)
      |                         ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void Trie::find_string(std::string&, std::string, int)':
selling_rna.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int i = 0; i < s.size(); i++)
      |                         ~~^~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::find_string1(std::string&)':
selling_rna.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for (int i = 0; i < s.size(); i++)
      |                         ~~^~~~~~~~~~

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