Submission #1131059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131059		Hamed_Ghaffari	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1600 ms	126744 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")

using ll = long long;
using pii = pair<int, int>;

#define X first
#define Y second
#define SZ(x) int(x.size())
#define pb push_back
#define Mp make_pair

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MXN = 1e5+5;

ll mod[2] = {1000000007, 998244353};
using Hash = pair<ll, ll>;
Hash operator+(Hash A, Hash B) {
  return Hash((A.X+B.X)%mod[0], (A.Y+B.Y)%mod[1]);
}
Hash operator*(Hash A, Hash B) {
  return Hash(A.X*B.X%mod[0], A.Y*B.Y%mod[1]);
}
Hash P;
bool is_prime(int x) {
  for(int i=2; i*i<=x; i++)
    if(x%i==0)
      return 0;
  return 1;
}
void init_hash() {
  P.X = rng()%200+100;
  while(!is_prime(P.X)) P.X++;
  P.Y = rng()%200+100;
  while(P.X==P.Y || !is_prime(P.Y)) P.Y++;
}
Hash get_hash(string s) {
  Hash res = Hash(0, 0);
  for(int i=SZ(s)-1; i>=0; i--)
    res = (res*P) + Hash{s[i], s[i]};
  return res;
}

int O[256];
char O_[4];
int timer;
vector<int> ch[4], cnt, stt, fnt;
int new_vertex() {
  for(int i=0; i<4; i++) ch[i].pb(0);
  cnt.pb(0);
  return SZ(cnt)-1;
}
void insert(string s) {
  int v=0;
  for(char c : s) {
    if(!ch[O[c]][v]) ch[O[c]][v] = new_vertex();
    v = ch[O[c]][v];
  }
  cnt[v]++;
}
void dfs(int v) {
  stt[v] = timer++;
  for(int i=0; i<4; i++)
    if(ch[i][v])
      dfs(ch[i][v]);
  fnt[v] = timer;
}
void init_trie() {
  stt.resize(SZ(cnt));
  fnt.resize(SZ(cnt));
  timer = 0;
  dfs(0);
}	

vector<pair<Hash, pii>> Q[MXN];
int n, m, ans[MXN];

void add(string p, string q, int i) {
  int v=0;
  for(char c : p) {
    if(!ch[O[c]][v]) return;
    v = ch[O[c]][v];
  }
  Q[fnt[v]-1].pb(Mp(get_hash(q), pii(1, i)));
  Q[stt[v]-1].pb(Mp(get_hash(q), pii(-1, i)));
}

map<Hash, int> hmap;
string path;

void solve(int v=0) {
  if(cnt[v]) {
    Hash hs = Hash(0, 0);
    for(int i=SZ(path)-1; i>=0; i--)
      hmap[hs = (hs*P) + Hash(path[i], path[i])] += cnt[v];
  }
  for(auto x : Q[stt[v]])
    ans[x.Y.Y] += x.Y.X*hmap[x.X];
  for(int i=0; i<4; i++)
    if(ch[i][v]) {
      path.pb(O_[i]);
      solve(ch[i][v]);
      path.pop_back();
    }
}

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  init_hash();
  O_[0]='A'; O_[O['C'] = 1]='C'; O_[O['G'] = 2]='G'; O_[O['U'] = 3]='U';
  
  cin >> n >> m;
  string s;
  new_vertex();
  for(int i=0; i<n; i++) {
    cin >> s;
    insert(s);
  }
  init_trie();
  string p, q;
  for(int i=0; i<m; i++) {
    cin >> p >> q;
    add(p, q, i);
  }
  solve();
  for(int i=0; i<m; i++)
    cout << ans[i] << '\n';
  return 0;
}

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