oj.uz

Submission #81802

# Submission time Handle Problem Language Result Execution time Memory
81802 2018-10-26T20:46:57 Z Bodo171 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1258 ms 873672 KB 
#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

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.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 360380 KB Output is correct
2 Correct 491 ms 361000 KB Output is correct
3 Correct 848 ms 572904 KB Output is correct
4 Correct 848 ms 572904 KB Output is correct
5 Correct 1148 ms 858888 KB Output is correct
6 Correct 1258 ms 873672 KB Output is correct
7 Correct 62 ms 873672 KB Output is correct
8 Correct 856 ms 873672 KB Output is correct
9 Correct 645 ms 873672 KB Output is correct
10 Correct 623 ms 873672 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 873672 KB Output is correct
2 Correct 24 ms 873672 KB Output is correct
3 Correct 23 ms 873672 KB Output is correct
4 Correct 18 ms 873672 KB Output is correct
5 Correct 22 ms 873672 KB Output is correct
6 Correct 25 ms 873672 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3576 KB Output is correct
2 Correct 5 ms 3704 KB Output is correct
3 Correct 5 ms 3776 KB Output is correct
4 Correct 5 ms 3776 KB Output is correct
5 Correct 5 ms 3776 KB Output is correct
6 Correct 5 ms 3776 KB Output is correct
7 Correct 5 ms 3776 KB Output is correct
8 Correct 543 ms 360380 KB Output is correct
9 Correct 491 ms 361000 KB Output is correct
10 Correct 848 ms 572904 KB Output is correct
11 Correct 848 ms 572904 KB Output is correct
12 Correct 1148 ms 858888 KB Output is correct
13 Correct 1258 ms 873672 KB Output is correct
14 Correct 62 ms 873672 KB Output is correct
15 Correct 856 ms 873672 KB Output is correct
16 Correct 645 ms 873672 KB Output is correct
17 Correct 623 ms 873672 KB Output is correct
18 Correct 26 ms 873672 KB Output is correct
19 Correct 24 ms 873672 KB Output is correct
20 Correct 23 ms 873672 KB Output is correct
21 Correct 18 ms 873672 KB Output is correct
22 Correct 22 ms 873672 KB Output is correct
23 Correct 25 ms 873672 KB Output is correct
24 Correct 441 ms 873672 KB Output is correct
25 Correct 479 ms 873672 KB Output is correct
26 Correct 443 ms 873672 KB Output is correct
27 Correct 689 ms 873672 KB Output is correct
28 Correct 169 ms 873672 KB Output is correct
29 Correct 61 ms 873672 KB Output is correct