Submission #682064

#	Time	Username	Problem	Language	Result	Execution time	Memory
682064		Pannda	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	798 ms	1048576 KiB

selling_rna

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

const int N = (int)1e5;

struct Trie {
    vector<array<int, 4>> trie;
    vector<bitset<N>> bs;

    Trie() : trie(1), bs(1) {}

    void add(int u, string &s, int i) {
        for (auto c : s) {
            if (!trie[u][c]) {
                trie[u][c] = trie.size();
                trie.push_back({});
                bs.push_back(bitset<N>());
            }
            u = trie[u][c];
            bs[u].set(i);
        }
    }

    int get(int u, string &s) {
        for (auto c : s) {
            if (!trie[u][c]) {
                return 0;
            }
            u = trie[u][c];
        }
        return u;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    Trie pref, suff;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (auto &ch : s) {
            if (ch == 'A') ch = 0;
            if (ch == 'G') ch = 1;
            if (ch == 'C') ch = 2;
            if (ch == 'U') ch = 3;
        }
        pref.add(0, s, i);
        reverse(s.begin(), s.end());
        suff.add(0, s, i);
    }

    while (q--) {
        string p, s;
        cin >> p >> s;
        reverse(s.begin(), s.end());

        for (auto &ch : p) {
            if (ch == 'A') ch = 0;
            if (ch == 'G') ch = 1;
            if (ch == 'C') ch = 2;
            if (ch == 'U') ch = 3;
        }

        for (auto &ch : s) {
            if (ch == 'A') ch = 0;
            if (ch == 'G') ch = 1;
            if (ch == 'C') ch = 2;
            if (ch == 'U') ch = 3;
        }

        int pref_id = pref.get(0, p);
        int suff_id = suff.get(0, s);

        bitset<N> key = pref.bs[pref_id] & suff.bs[suff_id];

        cout << key.count() << '\n';
    }
}

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