Submission #1129605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129605		halogenbr	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1602 ms	140112 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
int getNum(char f) {
    return f == 'A' ? 0 : f == 'U' ? 1 : f == 'G' ? 2 : 3;
}

struct node {
    int child[4][4];
    int cnt;
    node() : cnt(0) {
        memset(child, -1, sizeof(child));
    }
};

struct Trie {
    vector<node> pool;
    int root;

    Trie() {
        pool.emplace_back();
        root = 0;
    }

    void add(const string &s) {
        int u = root;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            int c1 = getNum(s[i]), c2 = getNum(s[n - i - 1]);
            if (pool[u].child[c1][c2] == -1) {
                pool[u].child[c1][c2] = pool.size();
                pool.emplace_back();
            }
            u = pool[u].child[c1][c2];
            pool[u].cnt++;
        }
    }

    int solve(const string &s, const string &v) {
        int u = root;
        int n = s.size(), m = v.size();
        int len = min(n, m), head = 0, tail = INT_MAX;
        string rv = v;
        reverse(rv.begin(), rv.end());
        for (int i = 0; i < len; ++i) {
            int c1 = getNum(s[i]), c2 = getNum(rv[i]);
            if (pool[u].child[c1][c2] == -1) return 0;
            u = pool[u].child[c1][c2];
        }
        head = pool[u].cnt;
        queue<int> q;
        q.push(u);
        if (n < m) {
            for (int i = n; i < m; ++i) {
                int c = getNum(rv[i]);
                int sz = q.size();
                for (int j = 0; j < sz; ++j) {
                    int top = q.front();
                    q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int nxt = pool[top].child[k][c];
                        if (nxt != -1) q.push(nxt);
                    }
                }
            }
        } else if (n > m) {
            for (int i = m; i < n; ++i) {
                int c = getNum(s[i]);
                int sz = q.size();
                for (int j = 0; j < sz; ++j) {
                    int top = q.front();
                    q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int nxt = pool[top].child[c][k];
                        if (nxt != -1) q.push(nxt);
                    }
                }
            }
        } else {
            return head;
        }
        if (q.empty()) return 0;
        tail = 0;
        while (!q.empty()) {
            int top = q.front();
            q.pop();
            tail += pool[top].cnt;
        }
        return min(head, tail);
    }
};

int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    Trie trie;
    int n,m;cin>>n>>m;
    while(n--) {
      string x;cin>>x;
      trie.add(x);
    }
    while(m--) {
      string u,v;cin>>u>>v;
      cout << trie.solve(u,v)<<'\n';
    }
    return 0;
}

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