Submission #1130242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130242		minahttoe	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1603 ms	195956 KiB

selling_rna

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

struct node{
    int child[4][4];
    int cnt;
} trie[2000005];

unordered_map<char,int> mp={{'A',0},{'G',1},{'C',2},{'U',3}};
char rna[4]={'A','G','C','U'};
string p,q,s[2000005];
int nnode,n,m,a,b;

int new_node(){
    nnode++;
    memset(trie[nnode].child, -1, sizeof trie[nnode].child);
    trie[nnode].cnt=0;
    return nnode;
}

void ins(string s){
    int cur=0;
    int n=s.size();
    for(int i=0; i<n; i++){
        int c1=mp[s[i]];
        int c2=mp[s[n-i-1]];
        if(trie[cur].child[c1][c2]==-1) trie[cur].child[c1][c2]=new_node();
        cur=trie[cur].child[c1][c2];
        trie[cur].cnt++;
    }
}

int dfs1(int u, int k){
    int ret=0;
    if(k==a-1) return trie[u].cnt;
    for(int i=0; i<4; i++){
        if(trie[u].child[mp[p[k+1]]][mp[rna[i]]]!=-1)
            ret+=dfs1(trie[u].child[mp[p[k+1]]][mp[rna[i]]],k+1);
    }
    return ret;
}

int dfs2(int u, int k){
    int ret=0;
    if(k==b-1) return trie[u].cnt;
    for(int i=0; i<4; i++){
        if(trie[u].child[mp[rna[i]]][mp[q[b-k-2]]]!=-1)
            ret+=dfs2(trie[u].child[mp[rna[i]]][mp[q[b-k-2]]],k+1);
    }
    return ret;
}

int solve(){
    int cur=0;
    for(int i=0; i<min(a,b); i++){
        int c1=mp[p[i]];
        int c2=mp[q[b-i-1]];
        if(trie[cur].child[c1][c2]==-1) return 0;
        cur=trie[cur].child[c1][c2];
    }
    if(a>b){
        int tmp=dfs1(cur,b-1);
        return tmp;
    }
    if(a<b){
        int tmp=dfs2(cur,a-1);
        return tmp;
    }
    return trie[cur].cnt;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    memset(trie[0].child, -1, sizeof(trie[0].child));
    trie[0].cnt=0;
    for(int i=1; i<=n; i++){
        cin>>s[i];
        ins(s[i]);
    }
    while(m--){
        cin>>p>>q;
        a=p.size(),b=q.size();
        cout<<solve()<<'\n';
    }
    return 0;
}

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