#include <bits/stdc++.h>
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>
using namespace std;
void setio (string name) {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (name.size()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
ll cast (char c) {
switch (c)
{
case 'A':
return 0;
case 'C':
return 1;
case 'G':
return 2;
case 'U':
return 3;
}
}
struct Trie {
struct Node {
ptr(Node) child[4];
set<ll> suf;
};
ptr(Node) root = ptr(Node) (new Node);
void add(string& s, ll i) {
ptr(Node) node = root;
for (auto it = s.begin(); it != s.end(); it++) {
if (!node->child[cast(*it)])
node->child[cast(*it)] = ptr(Node) (new Node);
node->child[cast(*it)]->suf.insert(i);
node = node->child[cast(*it)];
}
}
set<ll> get(string& s) {
ptr(Node) node = root;
for (auto it = s.begin(); it != s.end(); it++) {
if (!node->child[cast(*it)])
return {};
node = node->child[cast(*it)];
}
return node->suf;
}
};
struct RTrie {
struct Node {
ptr(Node) child[4];
set<ll> suf;
};
ptr(Node) root = ptr(Node) (new Node);
void add(string& s, ll i) {
ptr(Node) node = root;
for (auto it = s.rbegin(); it != s.rend(); it++) {
if (!node->child[cast(*it)])
node->child[cast(*it)] = ptr(Node) (new Node);
node->child[cast(*it)]->suf.insert(i);
node = node->child[cast(*it)];
}
}
set<ll> get(string& s) {
ptr(Node) node = root;
for (auto it = s.rbegin(); it != s.rend(); it++) {
if (!node->child[cast(*it)])
return {};
node = node->child[cast(*it)];
}
return node->suf;
}
};
struct QTrie {
struct Node {
ptr(Node) child[4];
vector<ll> flag;
};
ptr(Node) root = ptr(Node) (new Node);
void add(string& s, ll i) {
ptr(Node) node = root;
for (auto it = s.begin(); it != s.end(); it++) {
if (!node->child[cast(*it)])
node->child[cast(*it)] = ptr(Node) (new Node);
node = node->child[cast(*it)];
}
node->flag.push_back(i);
}
};
struct RQTrie {
struct Node {
ptr(Node) child[4];
vector<ll> flag;
};
ptr(Node) root = ptr(Node) (new Node);
void add(string& s, ll i) {
ptr(Node) node = root;
for (auto it = s.rbegin(); it != s.rend(); it++) {
if (!node->child[cast(*it)])
node->child[cast(*it)] = ptr(Node) (new Node);
node = node->child[cast(*it)];
}
node->flag.push_back(i);
}
};
ll n, m;
string s, t;
vector<set<ll>> pre, suf;
void explore(ptr(Trie::Node) snode, ptr(QTrie::Node) qnode) {
for (ll& i : qnode->flag)
pre[i] = snode->suf;
range(i, 0, 4) {
if (snode->child[i] && qnode->child[i])
explore(snode->child[i], qnode->child[i]);
}
}
void rexplore(ptr(RTrie::Node) snode, ptr(RQTrie::Node) qnode) {
for (ll& i : qnode->flag)
suf[i] = snode->suf;
range(i, 0, 4) {
if (snode->child[i] && qnode->child[i])
rexplore(snode->child[i], qnode->child[i]);
}
}
ll sunion (set<ll>& a, set<ll>& b) {
ll cnt = 0;
for (const ll& it : a) {
if (b.count(it))
cnt++;
}
return cnt;
}
void solve() {
cin >> n >> m;
Trie tr;
RTrie rtr;
range(i, 0, n) {
cin >> s;
tr.add(s, i);
rtr.add(s, i);
}
QTrie qtr;
RQTrie rqtr;
range(i, 0, m) {
cin >> s >> t;
qtr.add(s, i);
rqtr.add(t, i);
}
pre.resize(m);
suf.resize(m);
explore(tr.root, qtr.root);
rexplore(rtr.root, rqtr.root);
range(i, 0, m)
cout << sunion(pre[i], suf[i]) << '\n';
}
int main () {
setio("");
ll t = 1;
// cin >> t;
while (t--) solve();
}
Compilation message
selling_rna.cpp: In function 'void setio(std::string)':
selling_rna.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'long long int cast(char)':
selling_rna.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
38 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
856 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1298 ms |
601172 KB |
Output is correct |
| 2 |
Execution timed out |
1517 ms |
1048576 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
896 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
856 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1298 ms |
601172 KB |
Output is correct |
| 9 |
Execution timed out |
1517 ms |
1048576 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
