제출 #1002350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002350		nmts	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	93 ms	101196 KiB

selling_rna

#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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40