Submission #1226154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226154		Braabebo10	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1165 ms	1077860 KiB

selling_rna

#include<bits/stdc++.h>
#define ll int
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

bool check(string &s, string &suffix) {
    ll n = s.size(), m = suffix.size(), i = n - 1, j = m - 1;
    while (i >= 0 && j >= 0) {
        if (s[i] != suffix[j])return 0;
        i--, j--;
    }
    return (j == -1);
}

struct node1 {
    map<char, ll> mp;
    ll ends = 0;
    ll &operator[](char c) {
        return mp[c];
    }
};

struct miniTrie {
    vector<node1> tree;
    vector<string> strings;
    ll newNode() {
        tree.emplace_back();
        return tree.size() - 1;
    }

    miniTrie() {
        tree.clear();
        strings.clear();
        newNode();
    }

    void insert(string &s) {
        strings.push_back(s);
        reverse(all(s));
        ll u = 0;
        for (auto c: s) {
            if (!tree[u][c])
                tree[u][c] = newNode();
            u = tree[u][c];
            tree[u].ends++;
        }
    }

    ll get(string suffix) {
        reverse(all(suffix));
        ll u = 0;
        for (auto c: suffix) {
            if (!tree[u][c])return 0;
            u = tree[u][c];
        }
        return tree[u].ends;
    }

    ll size() {
        return strings.size();
    }
};

struct node {
    map<char, ll> mp;
    miniTrie a;
    vector<pair<string, ll> > qu;
    ll ends = 0;
    ll &operator[](char c) {
        return mp[c];
    }

    void insS(string &s) {
        a.insert(s);
    }

    void insQ(string &s, ll &idx) {
        qu.push_back({s, idx});
    }
};

struct Trie {
    vector<node> tree;
    ll newNode() {
        tree.emplace_back();
        return tree.size() - 1;
    }

    Trie() {
        tree.clear();
        newNode();
    }

    void insert(string &s) {
        ll u = 0;
        for (auto c: s) {
            if (!tree[u][c])
                tree[u][c] = newNode();
            u = tree[u][c];
        }
        tree[u].insS(s);
        tree[u].ends++;
    }

    ll get(string &suffix) {
        ll u = 0;
        for (auto c: suffix) {
            if (!tree[u][c])return 0;
            u = tree[u][c];
        }
        return tree[u].ends;
    }

    void query(string &prefix, string &suffix, ll &idx) {
        ll u = 0;
        for (auto c: prefix) {
            if (!tree[u][c])return;
            u = tree[u][c];
        }
        tree[u].insQ(suffix, idx);
    }

    void dfs(ll u, vector<ll> &res) {
        // cout << u << nl;
        for (auto [ch, v]: tree[u].mp) {
            if (!v)continue;
            // cout << ch << nl;
            dfs(v, res);
            if (tree[u].a.size() < tree[v].a.size())swap(tree[u].a, tree[v].a);
            for (auto s: tree[v].a.strings)tree[u].a.insert(s);
        }
        // cout << u << nl;
        // for (auto s: tree[u].a.strings)
        //     cout << s << nl;
        for (auto &[suffix, idx]: tree[u].qu) {
            res[idx] += tree[u].a.get(suffix);
            // for (auto s: tree[u].a.strings)
            //     res[idx] += check(s, suffix), cout << s << ' ' << suffix << ' ' << check(s, suffix) << nl;
        }
    }
};

int main() {
    baraa
    ll n, q;
    cin >> n >> q;
    Trie trie;
    for (ll i = 0; i < n; i++) {
        string s;
        cin >> s;
        trie.insert(s);
    }
    vector<ll> res(q);
    for (ll i = 0; i < q; i++) {
        string prefix, suffix;
        cin >> prefix >> suffix;
        trie.query(prefix, suffix, i);
    }
    trie.dfs(0, res);
    for (ll i: res)cout << i << nl;
    return 0;
}

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