Submission #1199113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199113		qrn	Selling RNA Strands (JOI16_selling_rna)	C++20	10 / 100	1609 ms	527912 KiB

selling_rna

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define pb push_back
#define ins insert
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 41;
const intt inf = 1e18;
const intt mxN = 5005;
const intt L = 21;

struct trie {
    map<intt, trie*> kids;
    set<intt> data;
    intt cnt;
    trie () {
        cnt = 0;
        data.clear();
        kids.clear();
    }
};

void add(trie *& root, string s, intt idx) {
    trie *node = root;
    intt N = (intt)s.size();
    for(intt i = 0; i < N; i++) {
        if(node->kids.find(s[i] - 'A' + 1) == node->kids.end()) {
            node->kids[s[i] - 'A' + 1] = new trie(); 
        }
        node = node->kids[s[i] - 'A' + 1];
        node->cnt++;
        node->data.insert(idx);
    }
}

set<intt> st;
intt ans;

void get_pre(trie *& root, string s) {
    trie *node = root;
    intt N = (intt)s.size();
    // cout << "WTF" << endl;
    for(intt i = 0; i < N; i++) {
        if(node->kids.find(s[i] - 'A' + 1) == node->kids.end()) {
            return;
        }
        node = node->kids[s[i] - 'A' + 1];
    }
    st = node->data;
}

void get_suf(trie *& root, string s) {
    trie *node = root;
    intt N = (intt)s.size();
    for(intt i = 0; i < N; i++) {
        if(node->kids.find(s[i] - 'A' + 1) == node->kids.end()) {
            return;
        }
        node = node->kids[s[i] - 'A' + 1];
    }

    set<intt> temp = node->data;
    for(intt i : temp) {
        if(st.find(i) != st.end()) {
            ans++;
        }
    }
}

void solve() {
    intt N, M;
    cin >> N >> M;
    trie *root1 = new trie();
    trie *root2 = new trie();

    for(intt i = 0; i < N; i++) {
        string s;
        cin >> s;
        add(root1, s, i);
        reverse(ALL(s));
        // cout << i << endl;
        add(root2, s, i);
    }

    for(intt i = 0; i < M; i++) {
        string pre, suf;
        cin >> pre >> suf;
        get_pre(root1, pre);
        reverse(ALL(suf));
        // if(i == 1) {
        //     cout << "ST: ";
        //     for(intt i : st) {
        //         cout << i << " ";
        //     }
        //     cout << endl;
        // }
        get_suf(root2, suf);
        cout << ans << endl;
        st.clear();
        ans = 0;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

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