oj.uz

Submission #1112555

# Submission time Handle Problem Language Result Execution time Memory
1112555 2024-11-14T10:20:16 Z fryingduc Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 206 ms 198216 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 132548 KB Output is correct
2 Correct 35 ms 132424 KB Output is correct
3 Correct 36 ms 132432 KB Output is correct
4 Correct 36 ms 132432 KB Output is correct
5 Correct 37 ms 132432 KB Output is correct
6 Correct 44 ms 130632 KB Output is correct
7 Correct 41 ms 132424 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 198216 KB Output is correct
2 Correct 181 ms 194888 KB Output is correct
3 Correct 201 ms 162464 KB Output is correct
4 Correct 188 ms 161608 KB Output is correct
5 Correct 164 ms 182088 KB Output is correct
6 Correct 166 ms 182856 KB Output is correct
7 Correct 105 ms 145992 KB Output is correct
8 Correct 177 ms 172440 KB Output is correct
9 Correct 185 ms 167340 KB Output is correct
10 Correct 168 ms 164424 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 131840 KB Output is correct
2 Correct 66 ms 131656 KB Output is correct
3 Correct 64 ms 131656 KB Output is correct
4 Correct 64 ms 131656 KB Output is correct
5 Correct 68 ms 131676 KB Output is correct
6 Correct 64 ms 131656 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 132548 KB Output is correct
2 Correct 35 ms 132424 KB Output is correct
3 Correct 36 ms 132432 KB Output is correct
4 Correct 36 ms 132432 KB Output is correct
5 Correct 37 ms 132432 KB Output is correct
6 Correct 44 ms 130632 KB Output is correct
7 Correct 41 ms 132424 KB Output is correct
8 Correct 204 ms 198216 KB Output is correct
9 Correct 181 ms 194888 KB Output is correct
10 Correct 201 ms 162464 KB Output is correct
11 Correct 188 ms 161608 KB Output is correct
12 Correct 164 ms 182088 KB Output is correct
13 Correct 166 ms 182856 KB Output is correct
14 Correct 105 ms 145992 KB Output is correct
15 Correct 177 ms 172440 KB Output is correct
16 Correct 185 ms 167340 KB Output is correct
17 Correct 168 ms 164424 KB Output is correct
18 Correct 63 ms 131840 KB Output is correct
19 Correct 66 ms 131656 KB Output is correct
20 Correct 64 ms 131656 KB Output is correct
21 Correct 64 ms 131656 KB Output is correct
22 Correct 68 ms 131676 KB Output is correct
23 Correct 64 ms 131656 KB Output is correct
24 Correct 194 ms 187344 KB Output is correct
25 Correct 183 ms 187424 KB Output is correct
26 Correct 183 ms 186696 KB Output is correct
27 Correct 206 ms 160368 KB Output is correct
28 Correct 172 ms 152940 KB Output is correct
29 Correct 110 ms 139196 KB Output is correct