Submission #597987

#	Time	Username	Problem	Language	Result	Execution time	Memory
597987		isaachew	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	258 ms	167840 KiB

selling_rna

#include <bits/stdc++.h>
/*
 Trie+suffix trie
 
 ST1: Brute force (O(n^2m))
 ST2: trie + suffix trie (O(nm))
 ST3: Search in order of customers + suffix trie + HLD? O(sum(|S_i|)log N+sum(|P_i|)+sum(|Q_i|))
 */
class trie{
public:
    trie* nchar[4];
    bool leaf;
    int count;//total count
    int scount;//count in this node
    std::vector<std::pair<std::string,int>> inps;
    trie():leaf(1),count(0),scount(0){
        
    }
    ~trie(){
        if(!leaf){
            for(int i=0;i<4;i++){
                delete nchar[i];
            }
        }
    }
    void split(){
        if(!leaf)return;
        leaf=0;
        for(int i=0;i<4;i++){
            nchar[i]=new trie;
        }
    }
    void merge(trie* oth){
        scount+=oth->scount;
        count+=oth->count;
        if(oth->leaf)return;
        split();
        for(int i=0;i<4;i++){
            nchar[i]->merge(oth->nchar[i]);
        }
    }
    void add(const char* ch,int cnt=1){
        count+=cnt;
        if(ch[0]=='\0'){
            scount+=cnt;
        }else{
            split();
            int ind=ch[0]=='A'?0:ch[0]=='C'?1:ch[0]=='G'?2:3;
            return nchar[ind]->add(ch+1,cnt);
        }
    }
    trie* fnode(const char* ch){
        if(ch[0]=='\0'){
            return this;
        }
        int ind=ch[0]=='A'?0:ch[0]=='C'?1:ch[0]=='G'?2:3;
        return nchar[ind]->fnode(ch+1);
    }
    
    int fcnt(const char* ch){
        if(ch[0]=='\0'){
            return count;
        }
        int ind=ch[0]=='A'?0:ch[0]=='C'?1:ch[0]=='G'?2:3;
        return nchar[ind]->fcnt(ch+1);
    }
};

std::vector<int> outarr;
trie* recurse(trie* cur,std::string& cst){
    
    trie* sft;
    if(cur->leaf){
        sft=new trie;
    }else{
    
        trie* stries[4];
        int b_ind=0;
        int b_cnt=-1;
        for(int i=0;i<4;i++){
            cst+="ACGU"[i];
            stries[i]=recurse(cur->nchar[i],cst);
            cst.resize(cst.size()-1);
            if(stries[i]->count>b_cnt){
                b_cnt=stries[i]->count;
                b_ind=i;
            }
        }
        sft=stries[b_ind];
        for(int i=0;i<4;i++){
            if(i==b_ind)continue;
            sft->merge(stries[i]);
            delete stries[i];
        }
    }
    if(cur->scount){//add reverse string
        char* rst=new char[cst.size()];
        for(int i=0;i<cst.size();i++){
            rst[i]=cst[cst.size()-i-1];
        }
        rst[cst.size()]='\0';//null terminate
        sft->add(rst,cur->scount);
        delete[] rst;
    }
    for(std::pair<std::string,int> i:cur->inps){
        char* rst=new char[i.first.size()];
        for(int j=0;j<i.first.size();j++){
            rst[i.first.size()-j-1]=i.first[j];
        }
        rst[i.first.size()]='\0';
        outarr[i.second]=sft->fcnt(rst);
    }
    return sft;
}
int main(){
    int n,m;
    std::cin>>n>>m;
    std::vector<std::string> strs;
    std::vector<std::pair<std::string,std::string>> prefs;
    trie root;
    for(int i=0;i<n;i++){
        std::string x;
        std::cin>>x;
        root.add(x.c_str());
        strs.push_back(x);
    }
    for(int i=0;i<m;i++){
        std::string x,y;
        std::cin>>x>>y;
        prefs.push_back({x,y});
        root.fnode(x.c_str())->inps.push_back({y,i});
    }
    outarr.resize(m);
    std::string st;
    trie* ftr=recurse(&root,st);
    delete ftr;
    for(int i=0;i<m;i++){
        std::cout<<outarr[i]<<'\n';
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'trie* recurse(trie*, std::string&)':
selling_rna.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for(int i=0;i<cst.size();i++){
      |                     ~^~~~~~~~~~~
selling_rna.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for(int j=0;j<i.first.size();j++){
      |                     ~^~~~~~~~~~~~~~~

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