Submission #1112555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112555		fryingduc	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	206 ms	198216 KiB

selling_rna

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
const int N = 2e6 + 6;
int n;
string s[maxn];
int q;
int ids[maxn];

vector<int> mrtee[N];

int tin[N], tout[N];
int timer;

struct node {
  int child[4];
  int exist;
  node() {
    memset(child, -1, sizeof(child));
    exist = 0;
  }
} root[N], root_suffix[N];
int num_nodes;
int add_prefix(string &s) {
  int p = 0;
  for(int i = 0; i < (int)s.size(); ++i) {
    int c = s[i] - 'a';
    if(root[p].child[c] == -1) {
      root[p].child[c] = ++num_nodes;
    }
    p = root[p].child[c];
  }
  ++root[p].exist;
  return p;
}
int suffix_nodes;
void add_suffix(string &s, int id) {
  int p = 0;
  for(int i = (int)s.size() - 1; i >= 0; --i) {
    int c = s[i] - 'a';
    if(root_suffix[p].child[c] == -1) {
      root_suffix[p].child[c] = ++suffix_nodes;
    }
    p = root_suffix[p].child[c];
    mrtee[p].push_back(tin[id]);
  }
}
int find_prefix(string &s) {
  int p = 0;
  for(int i = 0; i < (int)s.size(); ++i) {
    int c = s[i] - 'a';
    if(root[p].child[c] == -1) {
      return -1;
    }
    p = root[p].child[c];
  }
  return p;
}
void build() {
  for(int i = 1; i <= suffix_nodes; ++i) {
    if((int)mrtee[i].size() < 2) continue;
    sort(mrtee[i].begin(), mrtee[i].end());
  }
}
int get_suffix(string &s, int l, int r) {
  int p = 0;
  for(int i = (int)s.size() - 1; i >= 0; --i) {
    int c = s[i] - 'a';
    if(root_suffix[p].child[c] == -1) {
      return 0;
    }
    p = root_suffix[p].child[c]; 
  }
  return upper_bound(mrtee[p].begin(), mrtee[p].end(), r) -
  lower_bound(mrtee[p].begin(), mrtee[p].end(), l);
}
void dfs(int u) {
  tin[u] = ++timer;
  for(int c = 0; c < 4; ++c) {
    if(root[u].child[c] != -1) {
      dfs(root[u].child[c]);
    }
  }
  tout[u] = timer;
}
void convert(string &s) {
  for(auto &c:s) {
    if(c == 'A') c = 'a';
    else if(c == 'U') c = 'b';
    else if(c == 'G') c = 'c';
    else c = 'd';
  }
}
void solve() {
  cin >> n >> q;
  for(int i = 1; i <= n; ++i) {
    cin >> s[i];
    convert(s[i]);
    ids[i] = add_prefix(s[i]);
  }
  dfs(0);
  for(int i = 1; i <= n; ++i) {
    add_suffix(s[i], ids[i]);
  }
  build();
  debug(num_nodes, suffix_nodes);
  string qp, qq;
  for(int i = 1; i <= q; ++i) {
    cin >> qp >> qq;
    convert(qp), convert(qq);
    int cur = find_prefix(qp);
    if(cur == -1) {
      cout << 0 << '\n';
      continue;
    }
    cout << get_suffix(qq, tin[cur], tout[cur]) << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40