# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
58450 | ruhanhabib39 | Selling RNA Strands (JOI16_selling_rna) | C++17 | 653 ms | 377776 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long Long;
int N, M;
char inp[100 * 1000 + 10];
char P[100 * 1000 + 10], Q[100 * 1000 + 10];
int V[256];
int ii = 0;
int lv = 0;
struct Trie {
Trie* nxt[4]; Trie* suff; int cc;
Trie() {
for(int i = 0; i < 4; i++) {
nxt[i] = NULL;
}
}
~Trie() {
for(int i = 0; i < 4; i++) {
if(nxt[i]) delete nxt[i];
}
}
};
Trie* pref;
int f() {
Trie *p = pref; int ln = strlen(P);
for(int i = 0; i < ln; i++) {
if(p->nxt[V[P[i]]] == NULL) return 0;
p = p->nxt[V[P[i]]];
}
Trie* s = p->suff;
if(s == NULL) return 0;
ln = strlen(Q);
for(int i = ln-1; i >= 0; i--) {
if(s->nxt[V[Q[i]]] == NULL) return 0;
s = s->nxt[V[Q[i]]];
}
return s->cc;
}
Trie* mix(Trie* a, Trie* b) {
if(b == NULL) return a;
if(a == NULL) return b;
Trie* t = new Trie();
t->cc = a->cc + b->cc;
for(int i = 0; i < 4; i++) {
t->nxt[i] = mix(a->nxt[i], b->nxt[i]);
}
return t;
}
// merges the suffixes of trie a, b into a
void merge(Trie* a, Trie* b) {
if(b == NULL) return;
if(a->suff == NULL) {
a->suff = b->suff;
return;
}
if(b->suff == NULL) return;
a->suff = mix(a->suff, b->suff);
}
void dfs(Trie* t) {
if(!t) return;
for(int i = 0; i < 4; i++) {
dfs(t->nxt[i]);
merge(t, t->nxt[i]);
}
}
int main() {
V['A'] = 0; V['G'] = 1; V['C'] = 2; V['U'] = 3;
pref = new Trie();
scanf("%d%d", &N, &M);
for(int i = 0; i < N; i++) {
scanf("%s", inp); int ln = strlen(inp);
Trie* cn = pref;
for(int j = 0; j < ln; j++) {
// cerr << "Prefix Adding " << inp[j] << "\n";
cn->cc++;
int vi = V[inp[j]];
if(cn->nxt[vi] == NULL) cn->nxt[vi] = new Trie();
cn = cn->nxt[vi];
}
cn->cc++;
if(cn->suff == NULL) cn->suff = new Trie();
Trie* sf = cn->suff;
for(int j = ln-1; j >= 0; j--) {
sf->cc++;
int vj = V[inp[j]];
if(sf->nxt[vj] == NULL) sf->nxt[vj] = new Trie();
sf = sf->nxt[vj];
}
sf->cc++;
}
dfs(pref);
for(int i = 0; i < M; i++) {
scanf("%s %s", P, Q);
printf("%d\n", f());
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |