oj.uz

Submission #1002350

# Submission time Handle Problem Language Result Execution time Memory
1002350 2024-06-19T13:09:03 Z nmts Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 93 ms 101196 KB 
#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
    TrieNode* child[4];
    int cnt;
    TrieNode() {
        for (int i = 0; i < 4; ++i) child[i] = nullptr;
        cnt = 0;
    }
};

class Trie {
    TrieNode* root;

    int charToIndex(char c) {
        if (c == 'A') return 0;
        if (c == 'G') return 1;
        if (c == 'C') return 2;
        if (c == 'U') return 3;
        return -1; // This should not happen
    }

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string s) {
        TrieNode* node = root;
        for (char c : s) {
            int index = charToIndex(c);
            if (!node->child[index]) {
                node->child[index] = new TrieNode();
            }
            node = node->child[index];
            node->cnt++;
        }
    }

    int search(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = charToIndex(c);
            if (!node->child[index]) {
                return 0;
            }
            node = node->child[index];
        }
        return node->cnt;
    }
};

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

    int N, M;
    cin >> N >> M;

    vector<string> RNA(N);
    for (int i = 0; i < N; ++i) {
        cin >> RNA[i];
    }

    vector<pair<string, string>> orders(M);
    for (int j = 0; j < M; ++j) {
        cin >> orders[j].first >> orders[j].second;
    }

    Trie prefixTrie, suffixTrie;
    for (const string& s : RNA) {
        prefixTrie.insert(s);
        string reversed_s = s;
        reverse(reversed_s.begin(), reversed_s.end());
        suffixTrie.insert(reversed_s);
    }

    for (const auto& order : orders) {
        const string& P = order.first;
        string Q = order.second;
        reverse(Q.begin(), Q.end());

        int prefixCount = prefixTrie.search(P);
        int suffixCount = suffixTrie.search(Q);

        cout << min(prefixCount, suffixCount) << '\n';
    }

    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5720 KB Output is correct
2 Incorrect 10 ms 3928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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