oj.uz

Submission #848985

# Submission time Handle Problem Language Result Execution time Memory
848985 2023-09-13T19:32:15 Z alexdd Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 343992 KB 
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const int cst = 31;
int n,m;
vector<int> trie[2000005];
int mch[2000005][26];
int rez[100005];
int cnt;
vector<int> suffs[2000005];
vector<pair<int,int>> qrys[2000005];
map<int,int> fr[2000005];
void dfs(int nod)
{
    int heavy=-1,maxc=-1;
    for(auto adj:trie[nod])
    {
        dfs(adj);
        if((int)fr[adj].size()>maxc)
            maxc=fr[adj].size(),heavy=adj;
    }
    if(heavy!=-1)
    {
        swap(fr[nod],fr[heavy]);
        for(auto adj:trie[nod])
            if(adj!=heavy)
            {
                for(auto it:fr[adj])
                    fr[nod][it.first]+=it.second;
                fr[adj].clear();
            }
    }
    for(auto x:suffs[nod])
        fr[nod][x]++;
    for(auto x:qrys[nod])
    {
        rez[x.second] = fr[nod][x.first];
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    string s,p,q;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        int nod=0;
        for(int j=0;j<s.size();j++)
        {
            if(mch[nod][s[j]-'A']==0)
            {
                cnt++;
                mch[nod][s[j]-'A']=cnt;
                trie[nod].push_back(cnt);
            }
            nod=mch[nod][s[j]-'A'];
        }
        int curaux=0,curp=1;
        for(int j=s.size()-1;j>=0;j--)
        {
            curaux = (curaux + (1LL*curp*(s[j]-'A'+1)%MOD))%MOD;
            curp=(curp*cst)%MOD;
            suffs[nod].push_back(curaux);
        }
    }
    for(int i=1;i<=m;i++)
    {
        cin>>p>>q;
        int nod=0;
        bool bl=0;
        for(int j=0;j<p.size();j++)
        {
            if(mch[nod][p[j]-'A']==0)
            {
                bl=1;
                break;
            }
            nod=mch[nod][p[j]-'A'];
        }
        if(!bl)
        {
            int curaux=0,curp=1;
            for(int j=q.size()-1;j>=0;j--)
            {
                curaux = (curaux + (1LL*curp*(q[j]-'A'+1)%MOD))%MOD;
                curp=(curp*cst)%MOD;
            }
            qrys[nod].push_back({curaux,i});
        }
    }
    dfs(0);
    for(int i=1;i<=m;i++)
        cout<<rez[i]<<"\n";
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j=0;j<s.size();j++)
      |                     ~^~~~~~~~~
selling_rna.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int j=0;j<p.size();j++)
      |                     ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 238080 KB Output is correct
2 Correct 51 ms 237940 KB Output is correct
3 Correct 47 ms 237916 KB Output is correct
4 Correct 48 ms 237904 KB Output is correct
5 Correct 47 ms 237908 KB Output is correct
6 Correct 47 ms 237908 KB Output is correct
7 Correct 49 ms 237916 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1526 ms 343992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 239820 KB Output is correct
2 Correct 61 ms 239656 KB Output is correct
3 Correct 61 ms 239824 KB Output is correct
4 Correct 56 ms 239468 KB Output is correct
5 Correct 61 ms 239668 KB Output is correct
6 Correct 60 ms 239728 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 238080 KB Output is correct
2 Correct 51 ms 237940 KB Output is correct
3 Correct 47 ms 237916 KB Output is correct
4 Correct 48 ms 237904 KB Output is correct
5 Correct 47 ms 237908 KB Output is correct
6 Correct 47 ms 237908 KB Output is correct
7 Correct 49 ms 237916 KB Output is correct
8 Execution timed out 1526 ms 343992 KB Time limit exceeded
9 Halted 0 ms 0 KB -