Submission #1208419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208419		minhpk	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1601 ms	184352 KiB

selling_rna

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,q;
int child[2000001][26];
string z[100005];
int cnt;
int mark[1000005];
int tour;
int sta[1000005];
int fin[1000005];
int ver[1000005];
unordered_map<int,vector<int>> m;
int mod=1e9+7;
int base=31;


void add(string& s,int pos){
    int k=0;
    for (auto c:s){
         if (!child[k][c-'A']){
             cnt++;
             child[k][c-'A']=cnt;
         }
         k=child[k][c-'A'];
    }
    mark[pos]=k;
}

void dfs(int k){
    tour++;
    sta[k]=tour;
    ver[tour]=k;

    for (int i=0;i<26;i++){
         if (child[k][i]){
             dfs(child[k][i]);
         }
    }

    fin[k]=tour;
}

int get(string& s,int val){
    int k=0;

    for (auto c:s){
         if (!child[k][c-'A']){
              return 0;
         }
         k=child[k][c-'A'];
    }
 //   cout << "ok" << "\n";
   // cout << m[val].size() << "\n";
    int pos=sta[k];
    int l=lower_bound(m[val].begin(),m[val].end(),pos)-m[val].begin();
    pos=fin[k];
    int r=upper_bound(m[val].begin(),m[val].end(),pos)-m[val].begin()-1;
    return r-l+1;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> q;
    for (int i=1;i<=a;i++){
         cin >> z[i];
         add(z[i],i);
    }
    dfs(0);
    for (int i=1;i<=a;i++){
         int h=0;
         int pos=mark[i];
         pos=sta[pos];
         for (int j=z[i].size()-1;j>=0;j--){
             h=(h*base + (z[i][j]-'A'+1))%mod;
           //  cout << h << " ";
             m[h].push_back(pos);
         }
    }

    for (auto p:m){
        sort(m[p.first].begin(),m[p.first].end());
    }

    while (q--){
        string s,s1;
        cin >> s >> s1;
        int h=0;
        for (int i=s1.size()-1;i>=0;i--){
             h=(h*base + (s1[i]-'A'+1))%mod;
        }
       // cout << h << " ";
        cout <<  get(s,h) << "\n";
    }
    return 0;
}

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