Submission #1267933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267933		hellogf	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	890 ms	178020 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

int idx(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;
    return 3; // 'U'
}

struct Trie {
    vector<array<int,4>> Tree;   
    vector<vector<int>> sf;      

    Trie() {
        Tree.reserve(4);
        sf.reserve(4);
        Tree.push_back({-1,-1,-1,-1});
        sf.push_back(vector<int>());
    }

    void reserve_nodes(size_t expect) {
        Tree.reserve(expect);
        sf.reserve(expect);
    }

    void clear() {
        Tree.clear();
        sf.clear();
        Tree.push_back({-1,-1,-1,-1});
        sf.push_back(vector<int>());
    }

    void Insert(const string &s, int id) {
        int node = 0;
        for (char c : s) {
            int x = idx(c);
            if (Tree[node][x] == -1) {
                Tree[node][x] = (int)Tree.size();
                Tree.push_back({-1,-1,-1,-1});
                sf.push_back(vector<int>());
            }
            node = Tree[node][x];
            sf[node].push_back(id);
        }
    }

    int FindNode(const string &s) const {
        int node = 0;
        for (char c : s) {
            int x = idx(c);
            if (Tree[node][x] == -1) return -1;
            node = Tree[node][x];
        }
        return node;
    }
};

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<string> a(n+1);
    long long sumLen = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sumLen += (int)a[i].size();
    }

    
    Trie p, q;
    p.reserve_nodes((size_t)min<long long>(sumLen + 5, (long long)2e6));
    q.reserve_nodes((size_t)min<long long>(sumLen + 5, (long long)2e6));

    
    for (int i = 1; i <= n; ++i) p.Insert(a[i], i);

    
    vector<string> L(m+1), R(m+1);
    vector<int> pid(m+1, -1), qid(m+1, -1);
    for (int i = 1; i <= m; ++i) {
        cin >> L[i] >> R[i];
        pid[i] = p.FindNode(L[i]); 
    }

    
    for (int i = 1; i <= n; ++i) {
        string rs = a[i];
        reverse(rs.begin(), rs.end());
        q.Insert(rs, i);
    }

    
    unordered_map<long long,int> cache;
    cache.reserve(m * 2);

 
    for (int i = 1; i <= m; ++i) {
        if (pid[i] == -1) {
            cout << 0 << '\n';
            continue;
        }

        string rr = R[i];
        reverse(rr.begin(), rr.end());
        int qnode = q.FindNode(rr);
        qid[i] = qnode;

        if (qnode == -1) {
            cout << 0 << '\n';
            continue;
        }

        long long key = ( (long long)pid[i] << 32 ) ^ (unsigned long long)qnode;
        auto it = cache.find(key);
        if (it != cache.end()) {
            cout << it->second << '\n';
            continue;
        }

        const vector<int> &A = p.sf[pid[i]]; 
        const vector<int> &B = q.sf[qnode]; 

        // Nếu một trong hai rỗng thì 0
        if (A.empty() || B.empty()) {
            cache[key] = 0;
            cout << 0 << '\n';
            continue;
        }

       
        const vector<int> *small = &A, *large = &B;
        if (A.size() > B.size()) swap(small, large);

        int cnt = 0;
        for (int v : *small) {
            if (binary_search(large->begin(), large->end(), v)) ++cnt;
        }

        cache[key] = cnt;
        cout << cnt << '\n';
    }

    return 0;
}

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