Submission #1208423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208423		minhpk	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	512 ms	453884 KiB

selling_rna

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a, q;
int child[2000005][26];
string z[100005];
int cnt, markNode[1000005], sta[1000005], finNode[1000005], tour;
vector<pair<long long, int>> allPairs;
const int BASE = 31;

void add(const string &s, int idx)
{
    int u = 0;
    for (char c : s)
    {
        int d = c - 'A';
        if (!child[u][d])
            child[u][d] = ++cnt;
        u = child[u][d];
    }
    markNode[idx] = u;
}

void dfs(int u)
{
    sta[u] = ++tour;
    for (int d = 0; d < 26; ++d)
    {
        int v = child[u][d];
        if (v)
            dfs(v);
    }
    finNode[u] = tour;
}

int getCount(const string &pre, long long hq)
{
    int u = 0;
    for (char c : pre)
    {
        int d = c - 'A';
        if (!child[u][d])
            return 0;
        u = child[u][d];
    }
    int L = sta[u], R = finNode[u];
    auto lo = lower_bound(allPairs.begin(), allPairs.end(), make_pair(hq, -1LL));
    auto hi = upper_bound(allPairs.begin(), allPairs.end(), make_pair(hq, (int)1e9));
    if (lo == hi)
        return 0;
    auto it1 = lower_bound(lo, hi, make_pair(hq, L));
    auto it2 = upper_bound(lo, hi, make_pair(hq, R));
    return it2 - it1;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> q;
    for (int i = 1; i <= a; ++i)
    {
        cin >> z[i];
        add(z[i], i);
    }
    dfs(0);

    long long totalLen = 0;
    for (int i = 1; i <= a; ++i)
        totalLen += z[i].size();
    allPairs.reserve(totalLen);

    for (int i = 1; i <= a; ++i)
    {
        long long h = 0;
        int pos = sta[markNode[i]];
        for (int j = z[i].size() - 1; j >= 0; --j)
        {
            h = h * BASE + (z[i][j] - 'A' + 1);
            allPairs.emplace_back(h, pos);
        }
    }
    sort(allPairs.begin(), allPairs.end());

    while (q--)
    {
        string P, Q;
        cin >> P >> Q;
        long long hq = 0;
        for (int j = Q.size() - 1; j >= 0; --j)
            hq = hq * BASE + (Q[j] - 'A' + 1);
        cout << getCount(P, hq) << '\n';
    }
    return 0;
}

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