oj.uz

Submission #598006

# Submission time Handle Problem Language Result Execution time Memory
598006 2022-07-17T09:44:55 Z isaachew Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 501304 KB 
#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
    int tlen;//number of chars of this node
    std::vector<int>* inps;
    trie():leaf(1),count(0),scount(0),tlen(0),inps(NULL){
        
    }
    ~trie(){
        if(!leaf){
            for(int i=0;i<4;i++){
                delete nchar[i];
            }
        }
        if(inps!=NULL){
            delete inps;
        }
    }
    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;
        tlen+=oth->tlen;
        if(oth->leaf)return;
        split();
        for(int i=0;i<4;i++){
            nchar[i]->merge(oth->nchar[i]);
        }
    }
    void add(const char* ch,int len=0,int cnt=1){
        count+=cnt;
        tlen+=len*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,len-1,cnt);
        }
    }
    trie* fnode(const char* ch){
        if(ch[0]=='\0'){
            return this;
        }
        if(leaf)return 0;
        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;
        }
        if(leaf)return 0;
        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;
std::vector<std::pair<std::string,std::string>> prefs;
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]->tlen>b_cnt){
                b_cnt=stries[i]->tlen;
                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()+1];
        for(int i=0;i<cst.size();i++){
            rst[i]=cst[cst.size()-i-1];
        }
        rst[cst.size()]='\0';//null terminate
        sft->add(rst,cst.size(),cur->scount);
        delete[] rst;
    }
    if(cur->inps==NULL)return sft;
    for(int i:*cur->inps){
        std::string x=prefs[i].second;
        char* rst=new char[x.size()+1];
        for(int j=0;j<x.size();j++){
            rst[x.size()-j-1]=x[j];
        }
        rst[x.size()]='\0';
        outarr[i]=sft->fcnt(rst);
    }
    return sft;
}
int main(){
    int n,m;
    std::cin>>n>>m;
    std::vector<std::string> strs;
    trie root;
    for(int i=0;i<n;i++){
        std::string x;
        std::cin>>x;
        root.add(x.c_str(),x.size());
        strs.push_back(x);
    }
    for(int i=0;i<m;i++){
        std::string x,y;
        std::cin>>x>>y;
        prefs.push_back({x,y});
        trie* ftr=root.fnode(x.c_str());
        if(ftr->inps==NULL){
            ftr->inps=new std::vector<int>();
            
        }
        ftr->inps->push_back(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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1187 ms 498788 KB Output is correct
2 Correct 1124 ms 471356 KB Output is correct
3 Execution timed out 1516 ms 501304 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 8268 KB Output is correct
2 Correct 34 ms 5600 KB Output is correct
3 Correct 38 ms 7996 KB Output is correct
4 Correct 28 ms 5856 KB Output is correct
5 Correct 30 ms 5772 KB Output is correct
6 Correct 34 ms 8388 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1187 ms 498788 KB Output is correct
9 Correct 1124 ms 471356 KB Output is correct
10 Execution timed out 1516 ms 501304 KB Time limit exceeded
11 Halted 0 ms 0 KB -