Submission #1182377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182377		tamatem	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1623 ms	861056 KiB

selling_rna

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

#define ll            long long int
const int maxN = 1e6+5;
int n;

map<char, int> mp;
void pre(){
    mp['A'] = 1;
    mp['C'] = 2;
    mp['G'] = 3;
    mp['T'] = 4;

}
struct Trie {
    struct Node {
        Node* child[5][5];
        int pre = 0;
        int is_word = 0;
 
        Node(){
            memset(child, 0, sizeof(child));
        }
    };

    Node* root;

    Trie(){
        root = new Node;
    }

    int count(string pre, string suf){
        Node* cur = root; 
        int n =  pre.size();
        int m = suf.size();
        for(int i =0; i<m; ++i){
            int x = mp[pre[i]];
            int y = mp[suf[i]];
            if(!cur->child[x][y])
                return 0;
            cur = cur->child[x][y];
        }
        queue<pair<Node*, int>> q;
        q.push(make_pair(cur, m));
        int ans = 0;
        while(q.size()){
            auto u = q.front();
            q.pop();
            Node* cur = u.first;
            int idx = u.second;
            if(idx==n){
                ans+=cur->pre;
                continue;
            }
            for(int i =0; i<4; ++i){
                if(cur->child[mp[pre[idx]]][i]){
                    Node*z = cur->child[mp[pre[idx]]][i];
                    q.push(make_pair(z, idx+1));
                }
            }
        }
        return ans;
    }
    
    void insert(const string &word){
        Node* cur = root; 
            cur -> pre++;
        int n = word.size();
        for(int i =0; i<n; ++i){
            int x = mp[word[i]];
            int y = mp[word[n-i-1]];
            if(! cur -> child[x][y]) 
                cur -> child[x][y] = new Node;
            cur = cur -> child[x][y];
            cur -> pre++;
        }
        cur -> is_word++;
    }
};
void doWork() {
    int m;
    cin >> n >> m;
    Trie tr1, tr2;
    for(int i =0; i<n; ++i){
        string s;
        cin >> s;
        tr1.insert(s);
        reverse(s.begin(), s.end());
        tr2.insert(s);
    }
    while(m--){
        string pref, suf;
        cin >> pref >> suf;
        reverse(suf.begin(), suf.end());
        if(pref.size()>=suf.size()){
            cout << tr1.count(pref, suf) << '\n';
        }
        else{
            cout << tr2.count(suf, pref) << '\n';
        }
    }
    
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    pre();
    int tt = 1;
    // cin >> tt;
    while (tt--) doWork();
    return 0;
}

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