Submission #81802

#	Time	Username	Problem	Language	Result	Execution time	Memory
81802		Bodo171	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	1258 ms	873672 KiB

selling_rna

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=100005;
char ch[]={'A','G','C','U'};
struct Trie
{
    Trie *son[4],*arb;
    int sum,ap,term;
    vector<int> qr;
    Trie()
    {
        for(int abc=0;abc<4;abc++)
            son[abc]=0;
        arb=0;
        sum=ap=term=0;
    }
}*rad=new Trie,*nil=new Trie;
int parse(char c)
{
    if(c=='A') return 0;
    if(c=='G') return 1;
    if(c=='C') return 2;
    return 3;
}
string s,a,aux;
string b[nmax];
int ans[nmax];
int wh,i,n,m;
void ins(Trie *nod,string s)
{
    nod->sum+=s.size();
    for(int idx=0;idx<s.size();idx++)
    {
        wh=parse(s[idx]);
        if(!nod->son[wh])
            nod->son[wh]=new Trie;
        nod=nod->son[wh];
        nod->ap++;
    }
    nod->term++;
}
void qr(Trie *nod,string s)
{
    for(int idx=0;idx<s.size();idx++)
    {
        wh=parse(s[idx]);
        if(!nod->son[wh])
            return;
        nod=nod->son[wh];
    }
    nod->qr.push_back(i);
}
int get_qr(Trie *nod,string s)
{
    for(int idx=0;idx<s.size();idx++)
    {
        wh=parse(s[idx]);
        if(!nod->son[wh])
            return 0;
        nod=nod->son[wh];
    }
    return nod->ap;
}
void mrg(Trie* &nou,Trie *vechi)
{
    nou->sum+=vechi->sum;
    nou->ap+=vechi->ap;
    for(int i=0;i<4;i++)
        if(vechi->son[i])
    {
        if(!nou->son[i])
            nou->son[i]=new Trie;
        mrg(nou->son[i],vechi->son[i]);
    }
}
void dfs(Trie* &nod)
{
    Trie *bigson=nil;
    int spec=-1;
    for(int i=0;i<4;i++)
        if(nod->son[i])
    {
        s+=ch[i];
        dfs(nod->son[i]);
        s.erase(s.end()-1);
        if(nod->son[i]->arb->sum>bigson->sum)
            bigson=nod->son[i]->arb,spec=i;
    }
    nod->arb=new Trie;
    nod->arb->sum=bigson->sum;
    for(int i=0;i<4;i++)
        nod->arb->son[i]=bigson->son[i];
    for(int i=0;i<4;i++)
        if(nod->son[i]&&spec!=i)
              mrg(nod->arb,nod->son[i]->arb);
    for(int i=0;i<nod->term;i++)
    {
        aux=s;
        reverse(aux.begin(),aux.end());
        ins(nod->arb,aux);
    }
    for(int i=0;i<nod->qr.size();i++)
        ans[nod->qr[i]]=get_qr(nod->arb,b[nod->qr[i]]);
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>s;
        ins(rad,s);
    }
    for(i=1;i<=m;i++)
    {
        cin>>a>>b[i];
        reverse(b[i].begin(),b[i].end());
        qr(rad,a);
    }
    s="";
    dfs(rad);
    for(i=1;i<=m;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void ins(Trie*, std::__cxx11::string)':
selling_rna.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int idx=0;idx<s.size();idx++)
                   ~~~^~~~~~~~~
selling_rna.cpp: In function 'void qr(Trie*, std::__cxx11::string)':
selling_rna.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int idx=0;idx<s.size();idx++)
                   ~~~^~~~~~~~~
selling_rna.cpp: In function 'int get_qr(Trie*, std::__cxx11::string)':
selling_rna.cpp:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int idx=0;idx<s.size();idx++)
                   ~~~^~~~~~~~~
selling_rna.cpp: In function 'void dfs(Trie*&)':
selling_rna.cpp:105:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<nod->qr.size();i++)
                 ~^~~~~~~~~~~~~~~

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