Submission #1226127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226127		Braabebo10	Selling RNA Strands (JOI16_selling_rna)	C++20	10 / 100	1600 ms	332724 KiB

selling_rna

#include<bits/stdc++.h>
#define ll long long
#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 node {
    map<char, ll> mp;
    vector<string> a;
    vector<pair<string, ll> > qu;
    ll ends = 0;
    ll &operator[](char c) {
        return mp[c];
    }

    void insS(string s) {
        a.push_back(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);
    }

    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) {
        for (auto [ch, v]: tree[u].mp) {
            if (!v)continue;
            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)tree[u].a.push_back(s);
        }
        for (auto &[suffix, idx]: tree[u].qu) {
            for (auto &s: tree[u].a)
                res[idx] += check(s, suffix);
        }
    }
};

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: 0 / 25
• Subtask 4: 0 / 40