oj.uz

Submission #748215

# Submission time Handle Problem Language Result Execution time Memory
748215 2023-05-25T16:29:16 Z oscarsierra12 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 600 ms 368156 KB 
#include <bits/stdc++.h>
using namespace std ;

#define ff    first
#define ss    second
#define pb    push_back

typedef long long    ll;
typedef pair<ll,ll>    ii;
typedef long double    lf;

const int N = 5e6;

const static int alpha = 26;
int trie[N][alpha], fail[N], nodes;
int matches[N];
vector <int> end_word[N];
int ans[N];
stack<int> st;

void add(string &s, int i) {
  int cur = 0;
  for(char c : s) {
    int x = c-'A';
    if(!trie[cur][x]) trie[cur][x] = ++nodes;
    cur = trie[cur][x];
  }
  //cnt_word[cur]++;
  end_word[cur].pb(i); // for i > 0
}

void build() {
  queue<int> q; q.push(0);
  while(q.size()) {
    int u = q.front(); q.pop();
    st.push(u);
    for(int i = 0; i < alpha; ++i) {
      int v = trie[u][i];
      if(!v) trie[u][i] = trie[ fail[u] ][i]; // construir automata
      else q.push(v);
      if(!u || !v) continue;
      fail[v] = trie[ fail[u] ][i];
      //fail_out[v] = end_word[ fail[v] ] ? fail[v] : fail_out[ fail[v] ];
      //cnt_word[v] += cnt_word[ fail[v] ]; // obtener informacion del fail_padre
    }
  }
}

void prop() { 
  while (st.size()) { 
     int u = st.top(); st.pop();
     for (auto &e : end_word[u]) ans[e] = matches[u];
     matches[fail[u]]+=matches[u];
  }
}

int main() {

  #ifdef LOCAL
  freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
  #endif // LOCAL

  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  
  int n, m; cin >> n >> m;
  //return 0;
  vector <string> s(n);
  for (auto &e : s) cin >> e;
  
  for (int i = 0; i < m; ++i) { 
     string prf, suf;
     cin >> prf >> suf;
     suf.pb('Z');
     suf = suf + prf;
     add(suf, i);
  }
  build();
  for (int i = 0; i < n; ++i) { 
     s[i] = s[i] + "Z" + s[i];
     int node = 0;
     for (auto &e : s[i]) 
        node = trie[node][e - 'A'], matches[node]++;
  }
  prop();
  
  for (int i = 0; i < m; ++i) cout << ans[i] << '\n';
  
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117772 KB Output is correct
2 Correct 58 ms 117792 KB Output is correct
3 Correct 59 ms 117744 KB Output is correct
4 Correct 60 ms 117708 KB Output is correct
5 Correct 73 ms 117696 KB Output is correct
6 Correct 59 ms 117760 KB Output is correct
7 Correct 57 ms 117728 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 151420 KB Output is correct
2 Correct 124 ms 139848 KB Output is correct
3 Correct 222 ms 195316 KB Output is correct
4 Correct 233 ms 196032 KB Output is correct
5 Correct 435 ms 267592 KB Output is correct
6 Correct 594 ms 266700 KB Output is correct
7 Correct 279 ms 241684 KB Output is correct
8 Correct 516 ms 327660 KB Output is correct
9 Correct 600 ms 368156 KB Output is correct
10 Correct 105 ms 131776 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 120476 KB Output is correct
2 Correct 74 ms 119684 KB Output is correct
3 Correct 79 ms 120284 KB Output is correct
4 Correct 73 ms 119644 KB Output is correct
5 Correct 72 ms 119756 KB Output is correct
6 Correct 77 ms 120080 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117772 KB Output is correct
2 Correct 58 ms 117792 KB Output is correct
3 Correct 59 ms 117744 KB Output is correct
4 Correct 60 ms 117708 KB Output is correct
5 Correct 73 ms 117696 KB Output is correct
6 Correct 59 ms 117760 KB Output is correct
7 Correct 57 ms 117728 KB Output is correct
8 Correct 146 ms 151420 KB Output is correct
9 Correct 124 ms 139848 KB Output is correct
10 Correct 222 ms 195316 KB Output is correct
11 Correct 233 ms 196032 KB Output is correct
12 Correct 435 ms 267592 KB Output is correct
13 Correct 594 ms 266700 KB Output is correct
14 Correct 279 ms 241684 KB Output is correct
15 Correct 516 ms 327660 KB Output is correct
16 Correct 600 ms 368156 KB Output is correct
17 Correct 105 ms 131776 KB Output is correct
18 Correct 80 ms 120476 KB Output is correct
19 Correct 74 ms 119684 KB Output is correct
20 Correct 79 ms 120284 KB Output is correct
21 Correct 73 ms 119644 KB Output is correct
22 Correct 72 ms 119756 KB Output is correct
23 Correct 77 ms 120080 KB Output is correct
24 Correct 124 ms 133200 KB Output is correct
25 Correct 141 ms 132180 KB Output is correct
26 Correct 124 ms 135372 KB Output is correct
27 Correct 139 ms 136568 KB Output is correct
28 Correct 162 ms 135732 KB Output is correct
29 Correct 123 ms 130204 KB Output is correct