oj.uz

Submission #1081437

# Submission time Handle Problem Language Result Execution time Memory
1081437 2024-08-30T04:54:19 Z MinhKien Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 403 ms 1048576 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1368 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 600 KB Output is correct
2 Correct 75 ms 25140 KB Output is correct
3 Correct 35 ms 14496 KB Output is correct
4 Correct 7 ms 612 KB Output is correct
5 Correct 78 ms 24924 KB Output is correct
6 Correct 32 ms 14496 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1368 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Runtime error 403 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -