Submission #580897

#	Time	Username	Problem	Language	Result	Execution time	Memory
580897		Jarif_Rahman	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	810 ms	326532 KiB

selling_rna

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll A = 11;
const ll B = 988144425;

int id(char c){
    if(c == 'A') return 0;
    if(c == 'C') return 1;
    if(c == 'G') return 2;
    return 3;
}

unordered_set<ll> st;

struct Trie{
    vector<vector<int>> trie;
    vector<unordered_map<ll, int>> sth;
    vector<vector<pair<ll, int>>>  queries;
    vector<int> ans;

    Trie(){
        trie.pb(vector<int>(4, -1));
        sth.pb(unordered_map<ll, int>());
        queries.pb(vector<pair<ll, int>>());
    }

    void add(str s){
        int nd = 0;
        for(int i = 0; i < s.size(); i++){
            if(trie[nd][id(s[i])] == -1){
                trie[nd][id(s[i])] = trie.size();
                sth.pb(unordered_map<ll, int>());
                queries.pb(vector<pair<ll, int>>());
                trie.pb(vector<int>(4, -1));
            }
            nd = trie[nd][id(s[i])];
        }
        ll h = 0;
        for(int i = int(s.size())-1; i >= 0; i--){
            h*=A, h%=B;
            h+=id(s[i])+1, h%=B;
            if(st.find(h) != st.end()) sth[nd][h]++;
        }
    }

    void add_query(int in, str p, ll h){
        int nd = 0;
        for(int i = 0; i < p.size(); i++){
            nd = trie[nd][id(p[i])];
            if(nd == -1) return;
        }
        queries[nd].pb({h, in});
    }

    void small_to_large(unordered_map<ll, int> &mp1, unordered_map<ll, int> &mp2){
        if(mp1.size() < mp2.size()) swap(mp1, mp2);
        for(auto [a, b]: mp2) mp1[a]+=b;
        mp2.clear();
    }

    void dfs(int nd = 0){
        for(int i = 0; i < 4; i++) if(trie[nd][i] != -1) dfs(trie[nd][i]);
        for(int i = 0; i < 4; i++) if(trie[nd][i] != -1) small_to_large(sth[nd], sth[trie[nd][i]]);
        for(auto [h, in]: queries[nd]) ans[in] = sth[nd][h];
    }

};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;

    Trie trie;
    trie.ans.resize(m, 0);

    vector<str> v;
    vector<pair<str, ll>> qq;

    for(int i = 0; i < n; i++){
        str s; cin >> s;
        v.pb(s);
    }

    for(int i = 0; i < m; i++){
        str p, q; cin >> p >> q;
        ll h = 0;
        for(int i = int(q.size())-1; i >= 0; i--){
            h*=A, h%=B;
            h+=id(q[i])+1, h%=B;
        }
        st.insert(h);
        qq.pb({p, h});
    }

    for(str s: v) trie.add(s);
    for(int i = 0; i < m; i++) trie.add_query(i, qq[i].f, qq[i].sc);

    trie.dfs();

    for(int x: trie.ans) cout << x << "\n";
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::add(str)':
selling_rna.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int i = 0; i < s.size(); i++){
      |                        ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void Trie::add_query(int, str, ll)':
selling_rna.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int i = 0; i < p.size(); i++){
      |                        ~~^~~~~~~~~~

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