Submission #1236394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236394		goldenbull	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	83 ms	126272 KiB

selling_rna

#include <bits/stdc++.h>

///----------------[shorthand macros]---------------------------------------
#define fi              first
#define se              second

#define pb              push_back
#define all(x)          x.begin(), x.end()
#define cast(a, b)      static_cast<a>(b)

#define MASK(n)        ((n >= 64 ? ~0ULL : ((1ULL << (n)) - 1ULL)))
#define BIT(n, i)      (((n) >> (i)) & 1)
#define SET(n, i)      (n = ((n) | (1 << (i))))
#define UNSET(n, i)    (n = ((n) & ~(1 << (i))))
#define FLIP(n, i)     (n = ((n) ^ (1 << (i))))

#define el '\n'

using namespace std;

///-------------[type aliases]------------------------------------
template <typename T>
using ve    = vector<T>;
using ll    = long long;
using ull   = unsigned ll;
using db    = double;
using vi    = ve<int>;
using vll   = ve<ll>;
using vdb   = ve<db>;
using vb    = ve<bool>;
using ii    = pair<int, int>;
using pll   = pair<ll, ll>;

///--------------------[constants]------------------------------------------
const ll MAX = 1e6 + 7;
const ll MOD = 1e9 + 7;
const ll inf = 2e9 + 7;

int mp[256];
char d[4] = {'A', 'C', 'G', 'U'};

///---------------------[structs]-------------------------------------------
struct Node
{
    Node* child[4];
    int ext;
    int st, w_cnt;
    Node() : ext(0), st(0), w_cnt(0)
    {
        for (int i = 0; i < 4; i++) child[i] = nullptr;
    }
};

struct Trie
{
    Node* root;
    int dfs_t;

    Trie() : dfs_t(0)
    {
        root = new Node();
    }

    void add(const string& s)
    {
        Node* p = root;
        for (auto i : s)
        {
            int c = mp[i];
            if (!p->child[c])
                p->child[c] = new Node();

            p = p->child[c];
        }
        p->ext++;
    }

    void sort_strings(Node* p, string& str, ve<string>& res)
    {
        p->w_cnt = p->ext;
        p->st = dfs_t;
        dfs_t += p->ext;

        for (int i = 0; i < p->ext; i++)
        {
            res.pb(str);
//            us[str] = res.size();
        }

        for (int i = 0; i < 4; i++)
        {
            if (!p->child[i]) continue;

            str += d[i];
            sort_strings(p->child[i], str, res);
            str.pop_back();

            p->w_cnt += p->child[i]->w_cnt;
        }
    }

    ii get_range(const string& s)
    {
        Node* p = root;
        for (auto i : s)
        {
            int c = mp[i];
            if (!p->child[c]) return ii(-1, -1);
            p = p->child[c];
        }
        return ii(p->st, p->st + p->w_cnt - 1);
    }
};

struct RevTrie
{
    Node* root;

    RevTrie()
    {
        root = new Node();
    }

    void add(const string& s)
    {
        Node* p = root;
        for (int i = s.size()-1; i >= 0; i--)
        {
            int c = mp[s[i]];
            if (!p->child[c])
                p->child[c] = new Node();

            p = p->child[c];
        }
        p->ext++;
    }

    bool get_all_suffix(
        Node* p, string& s, int i,
        string& str, ve<string>& res
    )
    {
        if (i < s.size())
        {
            int c = mp[s[i]];
            if (!p->child[c]) return false;
            str += s[i];
            get_all_suffix(p->child[c], s, i+1, str, res);
        }
        else
        {
            for (int j = 0; j < p->ext; j++)
            {
                res.pb(str);
            }

            for (int i = 0; i < 4; i++)
            {
                if (!p->child[i]) continue;
                str += d[i];
                get_all_suffix(p->child[i], s, inf, str, res);
                str.pop_back();
            }

            if (i != inf)
                for (auto& j : res) reverse(all(j));

            return true;
        }
    }
};

///---------------------[globals]-------------------------------------------
int n, m;
Trie T;
RevTrie rT;

///-----------------[helper functions]--------------------------------------

///------------------[main execution]---------------------------------------
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
//    freopen("test.inp", "r", stdin);
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);

    // preprocess
    mp['A'] = 0;
    mp['C'] = 1;
    mp['G'] = 2;
    mp['U'] = 3;

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string s; cin >> s;
        T.add(s);
        rT.add(s);
    }

    ve<string> sus;
    string tmp;
    T.sort_strings(T.root, tmp, sus);

    while (m--)
    {
        string s1, s2;
        cin >> s1 >> s2;
        reverse(all(s2));

        ii r = T.get_range(s1);

        ve<string> hcm;
        tmp = "";
        bool f1 = rT.get_all_suffix(rT.root, s2, 0, tmp, hcm);

//        cout << r.fi << ' ' << r.se << el;
//        cout << f1 << el;
//        for (auto i : hcm) cout << i << el;
//
//        cout << el;
        if (r.fi == -1 || !f1)
        {
            cout << 0 << el;
            continue;
        }

        int cnt = 0;
        for (auto i : hcm)
        {
            int id = lower_bound(all(sus), i) - sus.begin();
            if (id >= r.fi && id <= r.se)  cnt++;
        }

        cout << cnt << el;
    }

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'bool RevTrie::get_all_suffix(Node*, std::string&, int, std::string&, ve<std::__cxx11::basic_string<char> >&)':
selling_rna.cpp:148:27: warning: control reaches end of non-void function [-Wreturn-type]
  148 |             get_all_suffix(p->child[c], s, i+1, str, res);
      |             ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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