Submission #493173

#	Time	Username	Problem	Language	Result	Execution time	Memory
493173		alextodoran	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1598 ms	179192 KiB

selling_rna

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int M_MAX = 100000;

const int MOD = (int) 1e9 + 7;

int N, M;

string S[N_MAX + 2];
string P[M_MAX + 2], Q[M_MAX + 2];

int answer[M_MAX + 2];

int encrypt[CHAR_MAX];

vector <int> getSuffHash (string s) {
    vector <int> suffHash ((int) s.size());
    for (int i = (int) s.size() - 1; i >= 0; i--) {
        suffHash[i] = (i + 1 < (int) s.size() ? suffHash[i + 1] : 0);
        suffHash[i] = ((ll) 5 * suffHash[i] + (encrypt[s[i]] + 1)) % MOD;
    }
    return suffHash;
}

struct TrieNode {
    TrieNode* son[4];
    map <int, int> suffixes;
    vector <pair <int, int>> queries;
    TrieNode () {
        for (int enc = 0; enc < 4; enc++) {
            son[enc] = NULL;
        }
        suffixes.clear();
        queries.clear();
    }
};

TrieNode* root = new TrieNode;

void insertString (TrieNode* node, int id, string::iterator it) {
    if (it == S[id].end()) {
        vector <int> suffHash = getSuffHash(S[id]);
        for (int h : suffHash) {
            node->suffixes[h]++;
        }
        return;
    }
    int enc = encrypt[*it];
    if (node->son[enc] == NULL) {
        node->son[enc] = new TrieNode;
    }
    insertString(node->son[enc], id, next(it));
}
void insertString (int id) {
    insertString(root, id, S[id].begin());
}

void insertQuery (TrieNode* node, int id, string::iterator it) {
    if (it == P[id].end()) {
        int revHash = getSuffHash(Q[id]).front();
        node->queries.push_back({id, revHash});
        return;
    }
    int enc = encrypt[*it];
    if (node->son[enc] != NULL) {
        insertQuery(node->son[enc], id, next(it));
    }
}
void insertQuery (int id) {
    insertQuery(root, id, P[id].begin());
}

void solveQueries (TrieNode* node, map <int, int>* suffixes) {
    TrieNode* heavySon = NULL;
    for (int enc = 0; enc < 4; enc++) {
        if (node->son[enc] != NULL) {
            if (heavySon == NULL || (int) node->son[enc]->suffixes.size() > (int) heavySon->suffixes.size()) {
                heavySon = node->son[enc];
            }
        }
    }
    if (heavySon != NULL) {
        solveQueries(heavySon, suffixes);
    }
    for (int enc = 0; enc < 4; enc++) {
        if (node->son[enc] != NULL && node->son[enc] != heavySon) {
            map <int, int> sonSuffixes;
            solveQueries(node->son[enc], &sonSuffixes);
            for (pair <int, int> p : sonSuffixes) {
                (*suffixes)[p.first] += p.second;
            }
        }
    }
    for (pair <int, int> p : node->suffixes) {
        (*suffixes)[p.first] += p.second;
    }
    for (pair <int, int> q : node->queries) {
        answer[q.first] = (*suffixes)[q.second];
    }
}
void solveQueries () {
    map <int, int> suffixes;
    solveQueries(root, &suffixes);
}

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

    encrypt['A'] = 0;
    encrypt['C'] = 1;
    encrypt['G'] = 2;
    encrypt['U'] = 3;

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> P[i] >> Q[i];
    }

    for (int i = 0; i < N; i++) {
        insertString(i);
    }
    for (int i = 0; i < M; i++) {
        insertQuery(i);
    }
    solveQueries();
    for (int i = 0; i < M; i++) {
        cout << answer[i] << "\n";
    }

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'std::vector<int> getSuffHash(std::string)':
selling_rna.cpp:33:60: warning: array subscript has type 'char' [-Wchar-subscripts]
   33 |         suffHash[i] = ((ll) 5 * suffHash[i] + (encrypt[s[i]] + 1)) % MOD;
      |                                                            ^
selling_rna.cpp: In function 'void insertString(TrieNode*, int, std::__cxx11::basic_string<char>::iterator)':
selling_rna.cpp:61:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   61 |     int enc = encrypt[*it];
      |                       ^~~
selling_rna.cpp: In function 'void insertQuery(TrieNode*, int, std::__cxx11::basic_string<char>::iterator)':
selling_rna.cpp:77:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   77 |     int enc = encrypt[*it];
      |                       ^~~

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