oj.uz

Submission #682067

# Submission time Handle Problem Language Result Execution time Memory
682067 2023-01-15T14:50:24 Z Pannda Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 828 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = (int)1e5;
const int N2 = (int)5e3;

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

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

    void add(int u, string &s, int i, int subtask) {
        for (auto c : s) {
            if (!trie[u][c]) {
                trie[u][c] = trie.size();
                trie.push_back({});
                if (subtask == 2) {
                    bs2.push_back(bitset<N2>());
                } else {
                    bs.push_back(bitset<N>());
                }
            }
            u = trie[u][c];
            if (subtask == 2) {
                bs2[u].set(i);
            } else {
                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;
    int subtask = n <= N2 ? 2 : 6785;

    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, subtask);
        reverse(s.begin(), s.end());
        suff.add(0, s, i, subtask);
    }

    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);

        if (subtask == 2) {
            bitset<N2> key = pref.bs2[pref_id] & suff.bs2[suff_id];
            cout << key.count() << '\n';
        } else {
            bitset<N> key = pref.bs[pref_id] & suff.bs[suff_id];
            cout << key.count() << '\n';
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 828 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 948 KB Output is correct
2 Correct 231 ms 121644 KB Output is correct
3 Correct 240 ms 68376 KB Output is correct
4 Correct 167 ms 952 KB Output is correct
5 Correct 226 ms 72208 KB Output is correct
6 Correct 241 ms 68984 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Runtime error 828 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -