oj.uz

Submission #1081419

# Submission time Handle Problem Language Result Execution time Memory
1081419 2024-08-30T04:31:39 Z MinhKien Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 372 ms 1048576 KB 
#include <iostream>
#include <string>

using namespace std;

const int max_child = 676;

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(const string &pre, const int n, const string &suf, const int m, int &ans, const int i, node *cur) {
        if (i == max(n, m)) {
            ans += cur->cnt;
            return;
        }

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

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

int n, q;
string s, pre, suf;

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;
        
        int ans = 0;
        T.solve(pre, pre.length(), suf, suf.length(), ans, 0, T.root);

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

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 372 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -