제출 #1222278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222278		giorgi123glm	Selling RNA Strands (JOI16_selling_rna)	C++20	60 / 100	1597 ms	108044 KiB

selling_rna

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <functional>
#include <array>
using namespace std;

unordered_map <char, int> enhash = {
    {'A', 0},
    {'U', 1},
    {'G', 2},
    {'C', 3}
};

vector <char> dehash = {
    'A', 'U', 'G', 'C'  
};

const int lim = 2e6 + 10;

struct trie {
    int free_node = 1;
    vector <array <int, 4> > tree;
    vector <int> str_node;
    vector <char> node_col;
    vector <int> in;
    vector <int> out;

    trie (int num_str) {
        tree.resize (lim + 1);
        str_node.resize (num_str + 1);
        node_col.resize (lim + 1);
        node_col[0] = '.'; 
    };

    void add (string str, int ind) {
        int node = 0;
        for (int i = 0; i < str.size(); i++) {
            if (tree[node][enhash[str[i]]] == 0) {
                node_col[free_node] = str[i];
                tree[node][enhash[str[i]]] = free_node++;
            }
            node = tree[node][enhash[str[i]]];
        }

        str_node[ind] = node;
    }

    int traverse (string str) {
        int node = 0;
        for (int i = 0; i < str.size(); i++) {
            if (tree[node][enhash[str[i]]] == 0)
                return -1;
            node = tree[node][enhash[str[i]]];
        }
        return node;
    }

    void calc_dfs () {
        in.clear();
        out.clear();
        in.resize (lim + 1);
        out.resize (lim + 1);
        int timer = 0;

        function <void(int,int)> dfs =
        [&](int p, int par)->void {
            in[p] = out[p] = ++timer;
            for (int& e : tree[p])
                if (e != par && e != 0)
                    dfs (e, p);
            out[p] = timer;
        };
        dfs (0, 0);
    }

    void debug () {
        function <void(int,int,int)> dfs =
        [&](int p, int par, int dep)->void {
            cout << string (dep, '\t') << node_col[p] << ' ' << in[p] << ' ' << out[p] << '\n';
            for (int& e : tree[p])
                if (e != par && e != 0)
                    dfs (e, p, dep + 1);
        };
        dfs (0, 0, 0);
    }
};

int main () {
    int N = 0, Q = 0;
    cin >> N >> Q;

    vector <string> in (N + 1);
    for (int i = 1; i <= N; i++)
        cin >> in[i];

    trie preftrie (N + 1);
    trie sufftrie (N + 1);
    for (int i = 1; i <= N; i++) {
        preftrie.add (in[i], i);
        sufftrie.add ([](string str)->string {
            reverse (str.begin(), str.end());
            return str;
        }(in[i]), i);
    }
    preftrie.calc_dfs();
    sufftrie.calc_dfs();
    // preftrie.debug();
    // sufftrie.debug();

    vector <pair <int, int> > status (N + 1);
    for (int i = 1; i <= N; i++)
        status[i] = {
            preftrie.in[preftrie.str_node[i]],
            sufftrie.in[sufftrie.str_node[i]]
        };
    sort (status.begin() + 1, status.end());

    vector <array <int, 4> > q_in (Q + 1);
    for (int i = 1; i <= Q; i++) {
        string a = "", b = "";
        cin >> a >> b;

        reverse (b.begin(), b.end());

        int prefnode = preftrie.traverse (a);
        int suffnode = sufftrie.traverse (b);

        if (prefnode == -1 || suffnode == -1) {
            q_in[i] = {-1, -1, -1, -1};
            continue;
        }

        int& L1 = preftrie.in[prefnode], R1 = preftrie.out[prefnode];
        int& L2 = sufftrie.in[suffnode], R2 = sufftrie.out[suffnode];
        
        q_in[i] = {
            static_cast <int> (lower_bound (status.begin() + 1, status.end(), (pair <int, int>){L1, 0}) - status.begin()),
            static_cast <int> (lower_bound (status.begin() + 1, status.end(), (pair <int, int>){R1 + 1, 0}) - status.begin() - 1),
            L2, R2
        };
    }

    for (int i = 1; i <= Q; i++) {
        if (q_in[i][0] == -1) {
            cout << 0 << '\n';
            continue;
        }

        int ans = 0;
        for (int j = q_in[i][0]; j <= q_in[i][1]; j++)
            if (q_in[i][2] <= status[j].second && status[j].second <= q_in[i][3])
                ans++;
        cout << ans << '\n';
    }
}

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