Submission #404204

#	Time	Username	Problem	Language	Result	Execution time	Memory
404204		timmyfeng	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	216 ms	135552 KiB

selling_rna

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

const int N = 2000001, A = 4;
const string R = "AGCU";

int suffix[N][A], prefix[N][A], root[N], sub[N], ans[N];
vector<pair<int, vector<int>>> queries[N];

vector<int> read() {
    string s;
    cin >> s;

    vector<int> ans;
    for (auto c : s) {
        ans.push_back(find(R.begin(), R.end(), c) - R.begin());
    }

    return ans;
}

int merge(int u, int v) {
    if (u == 0 || v == 0) {
        return u > 0 ? u : v;
    } else {
        sub[u] += sub[v];
        for (int i = 0; i < A; ++i) {
            suffix[u][i] = merge(suffix[u][i], suffix[v][i]);
        }
        return u;
    }
}

void dfs(int u) {
    for (auto c : prefix[u]) {
        if (c > 0) {
            dfs(c);
            root[u] = merge(root[u], root[c]);
        }
    }

    for (auto &[i, q] : queries[u]) {
        int v = root[u];
        for (auto c : q) {
            v = suffix[v][c];
        }
        ans[i] = sub[v];
    }
}

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

    int n, m;
    cin >> n >> m;

    int x = 1, y = 1;
    for (int i = 0; i < n; ++i) {
        vector<int> s = read();

        int u = 0;
        for (auto c : s) {
            if (prefix[u][c] == 0) {
                prefix[u][c] = x++;
            }
            u = prefix[u][c];
        }

        if (root[u] == 0) {
            root[u] = y++;
        }

        reverse(s.begin(), s.end());
        u = root[u];
        ++sub[u];

        for (auto c : s) {
            if (suffix[u][c] == 0) {
                suffix[u][c] = y++;
            }
            u = suffix[u][c];
            ++sub[u];
        }
    }

    for (int i = 0; i < m; ++i) {
        vector<int> p = read(), q = read();

        int u = 0;
        for (auto c : p) {
            u = prefix[u][c];
        }

        if (u > 0) {
            reverse(q.begin(), q.end());
            queries[u].push_back({i, q});
        }
    }

    dfs(0);

    for (int i = 0; i < m; ++i) {
        cout << ans[i] << "\n";
    }
}

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