| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 339399 | ijxjdjd | Selling RNA Strands (JOI16_selling_rna) | Java | 0 ms | 0 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 long long ll;
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FR(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define RF(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
const int MAXN = (int)(1e5) + 5;
const int MAXNODES = (int)(2e6) + 5;
//const int MAXN = 5;
//const int MAXNODES = 20;
struct Node {
int to[4] = {-1, -1, -1, -1};
int leaf = -1;
int cnt = 0;
};
vi prefix[MAXN];
vi suffix[MAXN];
int cur[MAXN];
int ans[MAXN];
vector<Node> nodes;
vi ss[MAXN];
vi ssrev[MAXN];
struct Trie {
int root = -1;
vector<int> leaves;
int sz = 0;
bool st = false;
Trie() {
root = nodes.size();
nodes.push_back({});
}
int add(int i, vi& a) {
sz += a.size();
leaves.push_back(i);
return iter(root, 0, i, a);
}
int iter(int j, int cur, int i, vi& s) {
nodes[j].cnt++;
if (cur == s.size()) {
int old = nodes[j].leaf;
if (old == -1) {
nodes[j].leaf = i;
}
return old;
}
if (nodes[j].to[s[cur]] == -1) {
nodes[j].to[s[cur]] = nodes.size();
nodes.push_back({});
}
return iter(nodes[j].to[s[cur]], cur+1, i, s);
}
int cnt(vi& a, int u, int cur = 0) {
if (u == -1) {
return 0;
}
if (cur == a.size()) {
return nodes[u].cnt;
}
return cnt(a, nodes[u].to[a[cur]], cur+1);
}
};
Trie start;
Trie ts[MAXN];
int tr[MAXNODES];
int merge(int u, int j) {
if (ts[u].sz < ts[j].sz) {
swap(u, j);
}
trav(v, ts[j].leaves) {
ts[u].add(v, ssrev[v]);
}
return u;
}
void dfs(int u, vi& prefixes) {
if (nodes[u].leaf != -1) {
tr[u] = nodes[u].leaf;
}
vi send[5];
trav(a, prefixes) {
if (cur[a] == prefix[a].size()) {
send[4].push_back(a);
}
else {
send[prefix[a][cur[a]++]].push_back(a);
}
}
FR(i, 4) {
if (nodes[u].to[i] != -1) {
dfs(nodes[u].to[i], send[i]);
if (tr[u] == -1) {
tr[u] = tr[nodes[u].to[i]];
}
else {
tr[u] = merge(tr[u], tr[nodes[u].to[i]]);
}
}
}
trav(a, send[4]) {
ans[a] = ts[tr[u]].cnt(suffix[a], ts[tr[u]].root);
}
}
int conv[300];
int main() {
str s = "input.in";
freopen(s.c_str(), "r", stdin);
start.st = true;
int N, M;
memset(ans, 0, sizeof(ans));
cin >> N >> M;
conv['A'] = 0;
conv['G'] = 1;
conv['C'] = 2;
conv['U'] = 3;
FR(i, MAXNODES) {
tr[i] = -1;
}
FR(i, N) {
string t;
cin >> t;
FR(j, t.size()) {
ss[i].push_back(conv[t[j]]);
ssrev[i].push_back(conv[t[j]]);
}
reverse(ssrev[i].begin(), ssrev[i].end());
int o = start.add(i, ss[i]);
if (o == -1) {
ts[i].add(i, ssrev[i]);
}
else {
ts[o].add(i, ssrev[i]);
}
}
vi ori;
FR(i, M) {
string pre, suff;
cin >> pre >> suff;
FR(j, pre.size()) {
prefix[i].push_back(conv[pre[j]]);
}
FR(j, suff.size()) {
suffix[i].push_back(conv[suff[j]]);
}
reverse(suffix[i].begin(), suffix[i].end());
ori.push_back(i);
}
dfs(start.root, ori);
FR(i, M) {
cout << ans[i] << '\n';
}
}