oj.uz

Submission #598007

# Submission time Handle Problem Language Result Execution time Memory
598007 2022-07-17T10:11:30 Z isaachew Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 819 ms 179680 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){
        for(int i=0;i<4;i++){
            nchar[i]=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 split(int x){
        leaf=0;
        if(nchar[x]==NULL)nchar[x]=new trie;
    }
    void merge(trie* oth){
        scount+=oth->scount;
        count+=oth->count;
        tlen+=oth->tlen;
        for(int i=0;i<4;i++){
            if(oth->nchar[i]!=NULL){
                split(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{
            int ind=ch[0]=='A'?0:ch[0]=='C'?1:ch[0]=='G'?2:3;
            split(ind);
            return nchar[ind]->add(ch+1,len-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;
        if(nchar[ind]==NULL)return NULL;
        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;
        if(nchar[ind]==NULL)return 0;
        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++){
            if(cur->nchar[i]==NULL)continue;
            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(cur->nchar[i]==NULL)continue;
            if(i==b_ind)continue;
            sft->merge(stries[i]);
            delete stries[i];
        }
    }
    if(cur->scount){//add reverse string; input so fine
        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==NULL)continue;
        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:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for(int i=0;i<cst.size();i++){
      |                     ~^~~~~~~~~~~
selling_rna.cpp:126:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         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 340 KB Output is correct
4 Correct 1 ms 212 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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 129160 KB Output is correct
2 Correct 423 ms 122276 KB Output is correct
3 Correct 492 ms 130792 KB Output is correct
4 Correct 497 ms 124948 KB Output is correct
5 Correct 809 ms 176832 KB Output is correct
6 Correct 819 ms 179680 KB Output is correct
7 Correct 147 ms 9540 KB Output is correct
8 Correct 444 ms 99520 KB Output is correct
9 Correct 369 ms 85048 KB Output is correct
10 Correct 362 ms 87108 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8004 KB Output is correct
2 Correct 27 ms 4788 KB Output is correct
3 Correct 33 ms 7748 KB Output is correct
4 Correct 29 ms 5672 KB Output is correct
5 Correct 25 ms 4740 KB Output is correct
6 Correct 31 ms 7764 KB Output is correct

Subtask #4
40.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 340 KB Output is correct
4 Correct 1 ms 212 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 450 ms 129160 KB Output is correct
9 Correct 423 ms 122276 KB Output is correct
10 Correct 492 ms 130792 KB Output is correct
11 Correct 497 ms 124948 KB Output is correct
12 Correct 809 ms 176832 KB Output is correct
13 Correct 819 ms 179680 KB Output is correct
14 Correct 147 ms 9540 KB Output is correct
15 Correct 444 ms 99520 KB Output is correct
16 Correct 369 ms 85048 KB Output is correct
17 Correct 362 ms 87108 KB Output is correct
18 Correct 33 ms 8004 KB Output is correct
19 Correct 27 ms 4788 KB Output is correct
20 Correct 33 ms 7748 KB Output is correct
21 Correct 29 ms 5672 KB Output is correct
22 Correct 25 ms 4740 KB Output is correct
23 Correct 31 ms 7764 KB Output is correct
24 Correct 416 ms 108400 KB Output is correct
25 Correct 411 ms 112120 KB Output is correct
26 Correct 405 ms 109608 KB Output is correct
27 Correct 447 ms 112924 KB Output is correct
28 Correct 231 ms 36548 KB Output is correct
29 Correct 131 ms 18412 KB Output is correct