Submission #1258813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258813		damoon	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	618 ms	424840 KiB

selling_rna

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

#define pb push_back
#define pp pop_back

const int L=1e5+10,alp=4;
int n,m;
int ans[L];
vector<int> A[L],B[L],S[L];
map<char,int> MP;

struct trie{
    trie* ch[alp];
    int cnt;
    trie(){
        cnt=0;
        fill(ch,ch+alp,nullptr);
    }

    void spread(int c){
        if(ch[c] == nullptr){
            ch[c] = new trie();
        }
    }

    void put(vector<int>* x,int ind){
        cnt++;
        if(ind == -1)
            return;
        int c = (*x)[ind];
        spread(c);
        ch[c]->put(x,ind-1);
    }

    int get(vector<int>* x,int ind){
        if(ind == -1)
            return cnt;
        int c = (*x)[ind];
        if(ch[c] == nullptr)
            return 0;
        return ch[c]->get(x,ind-1);
    }

    void clear(){
        for(int c=0;c<alp;c++){
            if(ch[c] != nullptr){
                ch[c]->clear();
                delete ch[c];
                ch[c] = nullptr;
            }
        }
    }

    void prr(vector<int>* x){
        cout<<"node: ";
        for(auto i:(*x)){
            cout<<i;
        }
        cout<<endl;
        for(int c=0;c<alp;c++){
            if(ch[c] != nullptr){
                x->pb(c);
                ch[c]->prr(x);
                x->pp();
            }
        }
    }
};

struct triem{
    trie* t;
    triem* ch[alp];
    vector<int> Q;
    vector<int>* H;
    triem(){
        H = new vector<int>();
        t = new trie();
        fill(ch,ch+alp,nullptr);
    }

    void spread(int c){
        if(ch[c] == nullptr){
            ch[c] = new triem();
        }
    }

    void put(vector<int>* x,int ind,int i){
        if(ind == x->size()){
            H->pb(i);
            t->put(x,x->size()-1);
            return;
        }
        int c = (*x)[ind];
        spread(c);
        ch[c]->put(x,ind+1,i);
    }

    void putq(vector<int>* x,int ind,int i){
        if(ind == x->size()){
            Q.pb(i);
            return;
        }
        int c = (*x)[ind];
        spread(c);
        ch[c]->putq(x,ind+1,i);
    }

    void dfs(){
        for(int c=0;c<alp;c++){
            if(ch[c] == nullptr)
                continue;
            ch[c]->dfs();
            if(ch[c]->H->size() > H->size()){
                swap(ch[c]->H, H);
                swap(ch[c]->t, t);
            }
            for(auto i:*(ch[c]->H)){
                H->pb(i);
                t->put(&S[i],S[i].size()-1);
            }
            ch[c]->H->clear();
            ch[c]->t->clear();
        }

        /*
        if(Q.size()){
            vector<int> x;
            t->prr(&x);
        }
        */
        for(auto i:Q){
            ans[i] = t->get(&B[i],B[i].size()-1);
        }
    }
}T;

int main(){

    //ifstream cin ("in.in");
    MP['A'] = 0;
    MP['U'] = 1;
    MP['G'] = 2;
    MP['C'] = 3;

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string inp;
        cin>>inp;
        for(auto c:inp){
            S[i].pb(MP[c]);
        }
    }

    for(int i=1;i<=m;i++){
        string inp;
        cin>>inp;
        for(auto c:inp){
            A[i].pb(MP[c]);
        }
        cin>>inp;
        for(auto c:inp){
            B[i].pb(MP[c]);
        }
    }

    for(int i=1;i<=n;i++){
        T.put(&S[i],0,i);
    }
    for(int i=1;i<=m;i++){
        T.putq(&A[i],0,i);
    }

    T.dfs();

    for(int i=1;i<=m;i++){
        cout<<ans[i]<<endl;
    }
} 

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