Submission #768337

#	Time	Username	Problem	Language	Result	Execution time	Memory
768337		DylanSmith	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	425 ms	365524 KiB

selling_rna

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)
 
mt19937 rng;

typedef struct Node {
    int adj[4], par; int freq, pos;
    Node(int p = -1) {
        freq = 0; pos = -1; par = p;
        fill(adj, adj + 4, -1);
    }
} node;

int add(vector<node> &tree, string &s) {
    int cur = 0;
    for (char c : s) {
        if (tree[cur].adj[c - 'a'] == -1) {
            tree[cur].adj[c - 'a'] = sz(tree);
            tree.emplace_back(cur);
        }
        cur = tree[cur].adj[c - 'a'];
    }
    return cur;
}

int find(vector<node> &tree, string &s) {
    int cur = 0;
    for (char c : s) {
        if (tree[cur].adj[c - 'a'] == -1) return -1;
        cur = tree[cur].adj[c - 'a'];
    }
    return cur;
}

string convert(string s) {
    string res = "";
    for (char c : s) {
        if (c == 'A') res += 'a';
        else if (c == 'U') res += 'b';
        else if (c == 'G') res += 'c';
        else res += 'd';
    }
    return res;
}

void merge(vector<node> &tree1, vector<node> &tree2) {
    queue<int> q;
    q.push(0); q.push(0);
    while (!q.empty()) {
        int l = q.front(); q.pop();
        int r = q.front(); q.pop();
        tree1[l].freq += tree2[r].freq;
        for (int k = 0; k < 4; k++) {
            if (tree2[r].adj[k] != -1) {
                if (tree1[l].adj[k] == -1) {
                    tree1[l].adj[k] = sz(tree1);
                    tree1.emplace_back(l);
                }
                q.push(tree1[l].adj[k]);
                q.push(tree2[r].adj[k]);
            }
        }
    }
}

void solve() {
    int N, Q; cin >> N >> Q;
    vector<node> tree(1);
    vector<string> arr(N);
    for (int i = 0; i < N; i++) {
        string s; cin >> s;
        s = convert(s);
        arr[i] = s;
        int j = add(tree, s);
        tree[j].freq++;
        tree[j].pos = i;
    }
    vector<pair<string, string>> queries;
    vector<vector<int>> qMap(sz(tree));
    for (int q = 0; q < Q; q++) {
        string a, b; cin >> a >> b;
        a = convert(a); b = convert(b);
        queries.pb({a, b});
        qMap[find(tree, a)].pb(q);
    }
    vector<vector<node>> suf(sz(tree));
    vector<int> res(Q);
    for (int i = sz(tree) - 1; i > 0; i--) {
        suf[i] = vector<node>(1);
        if (tree[i].freq > 0) {
            string s2 = arr[tree[i].pos];
            reverse(all(s2));
            int j = add(suf[i], s2);
            while (j >= 0) {
                suf[i][j].freq += tree[i].freq;
                j = suf[i][j].par;
            }
        }
        for (int j = 0; j < 4; j++) {
            if (tree[i].adj[j] != -1) {
                if (sz(suf[tree[i].adj[j]]) > sz(suf[i]))
                    swap(suf[i], suf[tree[i].adj[j]]);
            }
        }
        for (int j = 0; j < 4; j++) {
            if (tree[i].adj[j] != -1) {
                merge(suf[i], suf[tree[i].adj[j]]);
            }
        }
        for (int q : qMap[i]) {
            string s2 = queries[q].second;
            reverse(all(s2));
            int j = find(suf[i], s2);
            res[q] = j == -1 ? 0 : suf[i][j].freq;
        }
    }
    for (int i : res) {
        cout << i << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
    
    solve();
 
    return 0;
}

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