Submission #1208434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208434		minhpk	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	674 ms	522580 KiB

selling_rna

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

const int MAXN = 2000005;
int a, q;
int child[MAXN][26];
string z[1000005];
int cnt;
int mark[1000005];
int tour;
int sta[MAXN], fin[MAXN], ver[MAXN];


vector<tuple<int,int,int>> m;

const int mod1 = 1000000007;
const int mod2 = 1000000009;
const int base1 = 31;
const int base2 = 37;

bool cmpHash(const tuple<int,int,int>& A, const tuple<int,int,int>& B) {
    if (get<0>(A) != get<0>(B))
        return get<0>(A) < get<0>(B);
    if (get<1>(A) != get<1>(B))
        return get<1>(A) < get<1>(B);
    return get<2>(A) < get<2>(B);
}

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

void dfs(int k){
    sta[k] = ++tour;
    ver[tour] = k;
    for (int i = 0; i < 26; i++){
        if (child[k][i]) dfs(child[k][i]);
    }
    fin[k] = tour;
}


int get(const string& s, int h1, int h2){
    int k = 0;
    for (char c : s){
        int idx = c - 'A';
        if (!child[k][idx]) return 0;
        k = child[k][idx];
    }
    int L = sta[k], R = fin[k];
    auto leftIt = lower_bound(m.begin(), m.end(),
        make_tuple(h1, h2, L),
        [](auto &A, auto &B){
            if (get<0>(A)!=get<0>(B)) return get<0>(A)<get<0>(B);
            if (get<1>(A)!=get<1>(B)) return get<1>(A)<get<1>(B);
            return get<2>(A)<get<2>(B);
        });
    auto rightIt = upper_bound(m.begin(), m.end(),
        make_tuple(h1, h2, R),
        [](auto &A, auto &B){
            if (get<0>(A)!=get<0>(B)) return get<0>(A)<get<0>(B);
            if (get<1>(A)!=get<1>(B)) return get<1>(A)<get<1>(B);
            return get<2>(A)<get<2>(B);
        });
    return rightIt - leftIt;
}

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);


    for (int i = 1; i <= a; i++){
        int node = mark[i];
        int pos = sta[node];
        int h1 = 0, h2 = 0;
        for (int j = (int)z[i].size() - 1; j >= 0; j--){
            int v = z[i][j] - 'A' + 1;
            h1 = (h1 * base1 + v) % mod1;
            h2 = (h2 * base2 + v) % mod2;
            m.emplace_back(h1, h2, pos);
        }
    }

    sort(m.begin(), m.end(), cmpHash);


    while (q--){
        string s, t;
        cin >> s >> t;
        int h1 = 0, h2 = 0;
        for (int i = (int)t.size() - 1; i >= 0; i--){
            int v = t[i] - 'A' + 1;
            h1 = (h1 * base1 + v) % mod1;
            h2 = (h2 * base2 + v) % mod2;
        }
        cout << get(s, h1, h2) << "\n";
    }

    return 0;
}

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