Submission #1081437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081437		MinhKien	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	403 ms	1048576 KiB

selling_rna

#include <iostream>
#include <string>

using namespace std;

const int max_child = 676;

string pre, suf;
int x, y;

struct Trie {
    struct node {
        node *child[max_child];
        int cnt;

        node () {
            fill_n(child, max_child, nullptr);
            cnt = 0;
        }
    };

    node *root;
    Trie () {
        root = new node();
    }

    void add_string(const string &s) {
        node *cur = root;

        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int p = (s[i] - 'A') * 26 + (s[n - i - 1] - 'A');

            if (cur->child[p] == nullptr) cur->child[p] = new node();

            cur = cur->child[p];
            ++cur->cnt;
        }
    }

    void solve(int &ans, const int i, node *cur) {
        if (i == max(x, y)) {
            ans += cur->cnt;
            return;
        }

        if (i < min(x, y)) {
            int p = (pre[i] - 'A') * 26 + (suf[y - i - 1] - 'A');

            if (cur->child[p] == nullptr) return;
            
            solve(ans, i + 1, cur->child[p]);
        } else {
            if (i < x) {
                for (int j = 0, p = (pre[i] - 'A') * 26; j < 26; ++j, ++p) {
                    if (cur->child[p] != nullptr) {
                        solve(ans, i + 1, cur->child[p]);
                    }
                }
            } else {
                for (int j = 0, p = suf[y - i - 1] - 'A'; j < 26; ++j, p += 26) {
                    if (cur->child[p] != nullptr) solve(ans, i + 1, cur->child[p]);
                }
            }
        }
    }
} T;

int n, q;
string s;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    cin >> n >> q;
    while (n--) {
        cin >> s;
        T.add_string(s);
    }

    while (q--) {
        cin >> pre >> suf;
        x = pre.length();
        y = suf.length();
        
        int ans = 0;
        T.solve(ans, 0, T.root);

        cout << ans << "\n";
    }

    return 0;
}

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