#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
// sad
map <char, char> mp = {
{ 'A', 'A' },
{ 'U', 'B' },
{ 'C', 'C' },
{ 'G', 'D' },
};
const ll MAXN = 2E5+16;
ll tin[MAXN][2];
ll tout[MAXN][2];
ll n;
vll vans;
ll timer=0;
bool isAnc (ll u, ll v, bool sad) {
return tin[u][sad] <= tin[v][sad] && tout[v][sad] <= tout[u][sad];
}
/* #define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
vll tree;
ll n;
SegTree (ll n): tree(2*n), n(n) {}
void pull (ll l, ll r, ll id) {
tree[id] = tree[id+1] + tree[id+off];
}
void update (ll at, ll val, ll l, ll r, ll id) {
if (at < l || r < at) return;
if (l == r) {
tree[id] += val;
return;
}
update(at, val, l, mid, id+1);
update(at, val, mid+1, r, id+off);
}
void update (ll at, ll val) {
update(at, val, 0, n-1, 0);
}
ll query (ll ql, ll qr, ll l, ll r, ll id) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return tree[id];
return query(ql, qr, l, mid, id+1) + query(ql, qr, mid+1, r, id+off);
}
ll query (ll ql, ll qr) {
return query(ql, qr, 0, n-1, 0);
}
} st(2*MAXN); */
struct Trie {
struct Node {
ll next[4]{};
vll ss;
vll qs;
Node () {}
};
vector <Node> tree;
ll nodes;
ll newNode () {
tree.push_back(Node());
return nodes++;
}
Trie (): nodes(0), tree(0) {
newNode();
}
void add (string str, ll i, bool isQ) {
ll id=0;
for (char &c : str) c=mp[c];
for (char c : str) {
if (!tree[id].next[c-'A']) tree[id].next[c-'A']=newNode();
id = tree[id].next[c-'A'];
}
(isQ ? tree[id].qs : tree[id].ss).push_back(i);
}
/* void dfs_ans (ll id) {
for (ll i : tree[id].qs) ::tin[i]=::timer++;
for (ll i : tree[id].ss) ::st.update(::tin[i], -1);
for (ll i = 0; i < 4; i++) {
if (!tree[id].next[i]) continue;
dfs_euler(tree[id].next[i]);
}
for (ll i : tree[id].ss) ::st.update(::tin[i], 1);
for (ll i : tree[id].qs) ::tout[i]=::timer++;
} */
void dfs_euler (ll id, bool sad) {
for (ll i : tree[id].qs) ::tin[i][sad]=::timer++;
for (ll i : tree[id].ss) ::tin[i][sad]=::timer++;
for (ll i = 0; i < 4; i++) {
if (!tree[id].next[i]) continue;
dfs_euler(tree[id].next[i], sad);
}
for (ll i : tree[id].ss) ::tout[i][sad]=::timer++;
for (ll i : tree[id].qs) ::tout[i][sad]=::timer++; // ideally in the reversed arary, but same thing
}
};
int main () {
cin.tie(nullptr) -> sync_with_stdio(false);
ll Q;
cin >> n >> Q;
vans.resize(Q, -16);
Trie norm, rev;
for (ll i = 0; i < n; i++) {
string str;
cin >> str;
norm.add(str, i, false);
reverse(str.begin(), str.end());
rev.add(str, i, false);
}
for (ll i = 0; i < Q; i++) {
string snorm, srev;
cin >> snorm >> srev;
reverse(srev.begin(), srev.end());
norm.add(snorm, i+n, true);
rev.add(srev, i+n, true);
}
norm.dfs_euler(0, false);
rev.dfs_euler(0, true);
for (ll i = 0; i < Q; i++) { // sad O(nQ) ;-;
ll ans=0;
for (ll j = 0; j < n; j++) {
if (isAnc(i+n, j, false) && isAnc(i+n, j, true)) ans++;
}
cout << ans <<'\n';
}
// st.update(tin[i], 1);
return 0;
}
Compilation message
selling_rna.cpp: In constructor 'Trie::Trie()':
selling_rna.cpp:70:8: warning: 'Trie::nodes' will be initialized after [-Wreorder]
70 | ll nodes;
| ^~~~~
selling_rna.cpp:69:19: warning: 'std::vector<Trie::Node> Trie::tree' [-Wreorder]
69 | vector <Node> tree;
| ^~~~
selling_rna.cpp:77:5: warning: when initialized here [-Wreorder]
77 | Trie (): nodes(0), tree(0) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
166172 KB |
Output is correct |
| 2 |
Correct |
269 ms |
165776 KB |
Output is correct |
| 3 |
Correct |
223 ms |
165548 KB |
Output is correct |
| 4 |
Correct |
251 ms |
166612 KB |
Output is correct |
| 5 |
Correct |
323 ms |
249132 KB |
Output is correct |
| 6 |
Correct |
332 ms |
251040 KB |
Output is correct |
| 7 |
Correct |
52 ms |
3148 KB |
Output is correct |
| 8 |
Correct |
242 ms |
126216 KB |
Output is correct |
| 9 |
Correct |
226 ms |
127700 KB |
Output is correct |
| 10 |
Correct |
149 ms |
127176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1560 ms |
7776 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
212 ms |
166172 KB |
Output is correct |
| 9 |
Correct |
269 ms |
165776 KB |
Output is correct |
| 10 |
Correct |
223 ms |
165548 KB |
Output is correct |
| 11 |
Correct |
251 ms |
166612 KB |
Output is correct |
| 12 |
Correct |
323 ms |
249132 KB |
Output is correct |
| 13 |
Correct |
332 ms |
251040 KB |
Output is correct |
| 14 |
Correct |
52 ms |
3148 KB |
Output is correct |
| 15 |
Correct |
242 ms |
126216 KB |
Output is correct |
| 16 |
Correct |
226 ms |
127700 KB |
Output is correct |
| 17 |
Correct |
149 ms |
127176 KB |
Output is correct |
| 18 |
Execution timed out |
1560 ms |
7776 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
