Submission #1276499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276499		papaulo	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	329 ms	280324 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#define MAXI 2100100
#define MAXM 100100
int trie[MAXI][4];
int mp[256];
vector<string> strs[MAXI];
int ans[MAXM];
int cnt[MAXI];
int sti[MAXI];
vector<int> trie2[MAXI][4];
vector<int> cnt2[MAXI];
vector<pair<int, string>> qs[MAXI];
int id=0;

void insert(string s) {
    int n=0;
    for(auto ch : s) {
        int &t=trie[n][mp[ch]];
        if(!t) {
            t=++id;
        }
        n=t;
        cnt[n]++;
    }
    reverse(s.begin(), s.end());
    strs[n].push_back(s);
}

void insert(int t, string s) {
    int n=0;
    for(auto ch : s) {
        int nxt=trie2[t][mp[ch]][n];
        if(!nxt) {
            nxt=trie2[t][mp[ch]].size();
            for(int i=0;i<4;i++) trie2[t][i].push_back(0);
            cnt2[t].push_back(0);
            trie2[t][mp[ch]][n]=nxt;
        }
        n=nxt;
        cnt2[t][n]++;
    }
}

int search(int t, string s) {
    int n=0;
    for(auto ch : s) {
        int nxt=trie2[t][mp[ch]][n];
        if(!t) {
           return 0;
        }
        n=nxt;
    }
    return cnt2[t][n];
}

void addQ(int i, string p, string q) {
    int n=0;
    for(auto ch : p) {
        int t=trie[n][mp[ch]];
        if(!t) return;
        n=t;
    }
    reverse(q.begin(), q.end());
    qs[n].push_back({i, q});
}

void dfs(int v) {
    int bst=0;
    for(int i=0;i<4;i++) {
        int t=trie[v][i];
        if(cnt[t]>cnt[bst]) bst=t;
    }
    if(!bst) {
        sti[v]=v;
        for(int i=0;i<4;i++) trie2[v][i].push_back(0);
        cnt2[v].push_back(0);
        for(auto s : strs[v]) insert(v, s);
        for(auto pr : qs[v]) {
            ans[pr.first]=search(v, pr.second);
        }
        return;
    }
    dfs(bst);
    sti[v]=sti[bst];
    for(int i=0;i<4;i++) {
        int t=trie[v][i];
        if(!t||t==bst) continue;
        dfs(t);
        for(int i=0;i<4;i++) trie2[sti[t]][i].clear();
        cnt2[sti[t]].clear();
        for(auto s : strs[sti[t]]) {
            insert(sti[v], s);
            strs[sti[v]].push_back(s);
        }
        strs[sti[t]].clear();
    }
    for(auto s : strs[v]) {
        insert(sti[v], s);
        strs[sti[v]].push_back(s);
    }
    for(auto pr : qs[v]) {
        ans[pr.first]=search(sti[v], pr.second);
    }
}

int main() {
    memset(trie, 0, sizeof(trie));
    memset(ans, 0, sizeof(ans));
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    mp['A']=0, mp['G']=1, mp['C']=2, mp['U']=3;
    int n, m;
    cin >> n >> m;
    while(n--) {
        string s;
        cin >> s;
        insert(s);
    }
    for(int i=0;i<m;i++) {
        string p, q;
        cin >> p >> q;
        addQ(i, p, q);
    }
    dfs(0);
    for(int i=0;i<m;i++) cout << ans[i] << "\n";
}

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