#include <bits/stdc++.h>
#define fi first
#define se second
#define task "RNA"
using namespace std;
const int N = 1e5;
int n, q, ans[2 * N];
string k[2 * N];
struct Trie
{
struct Node
{
int child[4];
int cnt;
} nodes[4 * N];
pair<int, vector<int>> endStr[4 * N];
vector<pair<string, int>> ask[4 * N];
int cur;
Trie() : cur(0)
{
memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
nodes[0].cnt = 0;
};
int new_node()
{
cur++;
nodes[cur].child[0] = nodes[cur].child[1] = nodes[cur].child[2] = nodes[cur].child[3] = -1;
nodes[cur].cnt = 0;
return cur;
}
int Pos(char k)
{
if (k == 'A')
return 0;
if (k == 'U')
return 1;
if (k == 'C')
return 3;
return 2;
}
void add_string(string &s, int posi)
{
int pos = 0, dem = 0;
for (int i = 0; i < s.size(); i++)
{
int c = Pos(s[i]);
if (nodes[pos].child[c] == -1)
nodes[pos].child[c] = new_node();
pos = nodes[pos].child[c];
nodes[pos].cnt++;
dem++;
}
endStr[pos].se.push_back(posi);
endStr[pos].fi += dem;
}
void find_string(string &s, string tmp, int l)
{
int pos = 0;
for (int i = 0; i < s.size(); i++)
{
int c = Pos(s[i]);
if (nodes[pos].child[c] == -1)
return;
pos = nodes[pos].child[c];
}
ask[pos].push_back({tmp, l});
}
int find_string1(string &s)
{
int pos = 0;
for (int i = 0; i < s.size(); i++)
{
int c = Pos(s[i]);
if (nodes[pos].child[c] == -1)
return 0;
pos = nodes[pos].child[c];
}
return nodes[pos].cnt;
}
bool delStr(int pos, string &s, int i)
{
if (i != (int)s.size())
{
int c = Pos(s[i]);
bool isChildDeleted = delStr(nodes[pos].child[c], s, i + 1);
if (isChildDeleted)
nodes[pos].child[c] = -1;
}
if (pos != 0)
{
nodes[pos].cnt--;
if (nodes[pos].cnt == 0)
return true;
}
return false;
}
} trie[2];
int dem = 0;
int In[2 * N], Out[2 * N], pos[2 * N];
int sz[2 * N];
void dfs(int u)
{
In[u] = ++dem;
pos[dem] = u;
sz[u] = trie[0].endStr[u].fi;
for (int i = 0; i <= 3; i++)
{
if (trie[0].nodes[u].child[i] == -1)
continue;
int x = trie[0].nodes[u].child[i];
// cout << u << x << '\n';
dfs(x);
sz[u] += sz[x];
}
Out[u] = dem;
}
void solve(int u)
{
for (auto i : trie[0].ask[u])
ans[i.se] = trie[1].find_string1(i.fi);
}
void dfs_solve(int u)
{
pair<int, int> big = {0, 0};
for (int i = 0; i <= 3; i++)
{
if (trie[0].nodes[u].child[i] == -1)
continue;
int x = trie[0].nodes[u].child[i];
if (big.fi < sz[x])
big = {sz[x], x};
}
for (int i = 0; i <= 3; i++)
{
if (trie[0].nodes[u].child[i] == -1)
continue;
int x = trie[0].nodes[u].child[i];
if (x != big.se)
{
dfs_solve(x);
for (int j = In[x]; j <= Out[x]; j++)
{
for (auto l : trie[0].endStr[pos[j]].se)
trie[1].delStr(0, k[l], 0);
}
}
}
if (big.se)
dfs_solve(big.se);
for (int i = 0; i <= 3; i++)
{
if (trie[0].nodes[u].child[i] == -1)
continue;
int x = trie[0].nodes[u].child[i];
if (x != big.se)
{
for (int j = In[x]; j <= Out[x]; j++)
{
for (auto l : trie[0].endStr[pos[j]].se)
trie[1].add_string(k[l], l);
}
}
}
for (auto l : trie[0].endStr[u].se)
trie[1].add_string(k[l], l);
solve(u);
return;
}
int main()
{
// freopen(task ".inp", "r", stdin);
// freopen(task ".out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> k[i];
trie[0].add_string(k[i], i);
reverse(k[i].begin(), k[i].end());
}
dfs(0);
for (int i = 1; i <= q; i++)
{
string u, v;
cin >> u >> v;
reverse(v.begin(), v.end());
trie[0].find_string(u, v, i);
}
dfs_solve(0);
for (int i = 1; i <= q; i++)
cout << ans[i] << '\n';
return 0;
}
Compilation message
selling_rna.cpp: In member function 'void Trie::add_string(std::string&, int)':
selling_rna.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void Trie::find_string(std::string&, std::string, int)':
selling_rna.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::find_string1(std::string&)':
selling_rna.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
56668 KB |
Output is correct |
| 2 |
Correct |
12 ms |
56668 KB |
Output is correct |
| 3 |
Correct |
12 ms |
56668 KB |
Output is correct |
| 4 |
Correct |
12 ms |
56760 KB |
Output is correct |
| 5 |
Correct |
13 ms |
56664 KB |
Output is correct |
| 6 |
Correct |
12 ms |
56852 KB |
Output is correct |
| 7 |
Correct |
13 ms |
56664 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
85 ms |
136712 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
60628 KB |
Output is correct |
| 2 |
Correct |
25 ms |
61380 KB |
Output is correct |
| 3 |
Correct |
27 ms |
61768 KB |
Output is correct |
| 4 |
Correct |
22 ms |
59236 KB |
Output is correct |
| 5 |
Correct |
26 ms |
61928 KB |
Output is correct |
| 6 |
Correct |
30 ms |
62116 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
56668 KB |
Output is correct |
| 2 |
Correct |
12 ms |
56668 KB |
Output is correct |
| 3 |
Correct |
12 ms |
56668 KB |
Output is correct |
| 4 |
Correct |
12 ms |
56760 KB |
Output is correct |
| 5 |
Correct |
13 ms |
56664 KB |
Output is correct |
| 6 |
Correct |
12 ms |
56852 KB |
Output is correct |
| 7 |
Correct |
13 ms |
56664 KB |
Output is correct |
| 8 |
Runtime error |
85 ms |
136712 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
