Submission #1183658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183658		peteza	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	813 ms	981712 KiB

selling_rna

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

int ans[100005];

struct node {
    int cnt = 0, sz=0;
    node* ptr[26] = {};
    vector<pair<string, int>> qrs;
    node* root;
} *root;

int n, q;
string str[100005];
string a, b;

void insa(node*&cur, string& toins, int idx, bool mode = 1) {
    if(!cur) cur = new node();
    cur->cnt++; cur->sz += toins.size();
    if(idx != toins.size()) {
        insa(cur->ptr[toins[idx]-'A'], toins, idx+1, mode);
    } else if(mode) {
        string &revver = toins;
        reverse(revver.begin(), revver.end());
        insa(cur->root, revver, 0, 0);
    }
}
string curs = "";

void traverse(node *&cur) {
    if(cur) cout << curs << '\n';
    else return ;
    for(int i=0;i<26;i++) {
        curs += 'A' + i;
        traverse(cur->ptr[i]);
        curs.pop_back();
    }
}

void marknode(node *&cur, string &a, string &b, int qridx, int idx) {
    if(!cur) return;
    if(idx == a.size()) {
        cur->qrs.emplace_back(b, qridx);
    } else marknode(cur->ptr[a[idx]-'A'], a, b, qridx, idx+1);
}

int match(node *&cur, string &a, int idx) {
    if(!cur) return 0;
    if(idx == a.size()) {return cur->cnt;}
    return match(cur->ptr[a[idx]-'A'], a, idx+1);
}

void mg(node *&added, node *&adder) {
    if(!adder) return;
    if(!added) {added = adder; return;}
    added->cnt += adder ->cnt;
    added->sz += adder->sz;
    for(int i=0;i<26;i++) mg(added->ptr[i], adder->ptr[i]);
}

int getsz(node *a) {
    return a ? a->sz : 0;
}

void dfsans(node *&cur) {
    if(!cur) return;
    for(int i=0;i<26;i++) {
        dfsans(cur->ptr[i]);
        if(cur->ptr[i]) {
            if(getsz(cur->root) < getsz(cur->ptr[i]->root)) swap(cur->ptr[i]->root, cur->root); 
        }
    }
    for(int i=0;i<26;i++) {
        if(cur->ptr[i])
            mg(cur->root, cur->ptr[i]->root);
    }
    for(auto &e:cur->qrs) {
        ans[e.second] = match(cur->root, e.first, 0);
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> q;
    for(int i=0;i<n;i++) {
        cin >> str[i];
        insa(root, str[i], 0);
    }
    for(int i=0;i<q;i++) {
        cin >> a >> b; reverse(b.begin(), b.end());
        marknode(root, a, b, i, 0);
    }
    dfsans(root);
    for(int i=0;i<q;i++) cout << ans[i] << '\n';
}

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