Submission #1194419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194419		anonymous321	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	709 ms	1114112 KiB

selling_rna

// https://oj.uz/problem/view/JOI16_selling_rna
#include <bits/stdc++.h>
using namespace std;

struct trie {
    vector<vector<int>> child {{-1, -1, -1, -1}};
    vector<vector<int>> s {{}};
    vector<vector<int>> ns {{}};
    vector<vector<int>> q {{}};
    vector<int> sz {0};
    vector<int> cnt {0};
};

vector<int> toc (26, -1);

vector<string> vs;
vector<string> vsr;
vector<string> vp;
vector<string> vq;
trie pref {};


void insert (trie &t, bool isq,bool iscnt, int &px, int szx, string &s, int id = 0, int i = 0) {
    if (!isq) {
        t.sz[i] += szx;
        t.s[i].push_back(px);
    }
    if (iscnt) t.cnt[i] += 1;
    if (id == s.size()) {
        if (isq) {
            t.q[i].push_back(px);
        } else {
            t.ns[i].push_back(px);
        }
        return;
    }
    int c = toc[s[id] - 'A'];
    if (t.child[i][c] == -1) {
        if (isq && !iscnt) return;
        t.child.push_back({-1, -1, -1, -1});
        t.s.push_back({});
        t.q.push_back({});
        t.sz.push_back(0);
        t.cnt.push_back(0);
        t.ns.push_back({});
        t.child[i][c] = t.child.size() - 1;
    }
    insert(t, isq, iscnt, px, szx, s, id+1, t.child[i][c]);
}

int query (trie &t, string&s, int id = 0, int i = 0) {
    if (id == s.size()) return t.cnt[i];
    int c = toc[s[id] - 'A'];
    if (t.child[i][c] == -1) return 0;
    else return query(t, s, id+1, t.child[i][c]);
}

vector<trie> dp;
vector<int> sol;

void comp (int i) {
    int max_sub = -1;
    int max_val = 1e9;
    for (int c = 0; c < 4; c++) {
        if (pref.child[i][c] != -1) {
            comp(pref.child[i][c]);
            if (pref.sz[i] > max_val) {
                max_val = pref.sz[i];
                max_sub = i;
            }
        }
    }
    if (max_sub != -1) {
        swap(dp[i], dp[pref.child[i][max_sub]]);
    }
    for (int c = 0; c < 4; c++) {
        if (c == max_sub) continue;
        if (pref.child[i][c] == -1) continue;
        for (auto &it : pref.s[pref.child[i][c]]) {
            insert(dp[i], true, true, it, 0, vsr[it]);
        }
    }
    for (auto &it : pref.ns[i]) {
        insert(dp[i], true, true, it, 0, vsr[it]);
    }
    for (auto &it : pref.q[i]) {
        sol[it] = query(dp[i], vq[it]);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    toc['A' - 'A'] = 0;
    toc['G' - 'A'] = 1;
    toc['C' - 'A'] = 2;
    toc['U' - 'A'] = 3;
    int n, m;
    cin >> n >> m;
    vs = vector<string> (n);
    vsr = vector<string> (n);
    for (int i = 0; i < n; i++) {
        cin >> vs[i];
        vsr[i] = vs[i];
        reverse(vsr[i].begin(), vsr[i].end());
        insert(pref, false, true, i, vs[i].size(), vs[i]);
    }
    vp = vector<string> (m);
    vq = vector<string> (m);
    for (int i = 0; i < m; i++) {
        cin >> vp[i] >> vq[i];
        reverse(vq[i].begin(), vq[i].end());
        insert(pref, true, false, i, vq[i].size(), vp[i]);
    }
    
    sol = vector<int> (m, 0);
    dp = vector<trie> (pref.child.size());
    comp(0);
    for (int i = 0; i < m; i++) {
        cout << sol[i] << "\n";
    }
    return 0;
}

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