Submission #1131227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131227		Hamed_Ghaffari	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	137 ms	64000 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
#define all(x) x.begin(), x.end()

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

const int MXN = 1e5+5;

int O[256];
char O_[4];

struct trie {
  vector<int> ch[4], cnt, sz;
  int new_vertex() {
    for(int i=0; i<4; i++) ch[i].pb(0);
    cnt.pb(0);
    sz.pb(0);
    return SZ(cnt)-1;
  }
  void insert(string s) {
    int v=0;
    sz[v]++;
    for(char c : s) {
      if(!ch[O[c]][v]) ch[O[c]][v] = new_vertex();
      v = ch[O[c]][v];
      sz[v]++;
    }
    cnt[v]++;
  }
  int get(string s) {
    int v=0;
    for(char c : s) {
      if(!ch[O[c]][v]) return 0;
      v = ch[O[c]][v];
    }
    return sz[v];
  }
} T1, T2;
int timer;
vector<int> stt, fnt;
void dfs(int v) {
  stt[v] = timer++;
  for(int i=0; i<4; i++)
    if(T1.ch[i][v])
      dfs(T1.ch[i][v]);
  fnt[v] = timer;
}
void init_trie() {
  stt.resize(SZ(T1.cnt));
  fnt.resize(SZ(T1.cnt));
  timer = 0;
  dfs(0);
}	
vector<pair<string, pii>> Q[MXN];
int n, m, ans[MXN];

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

string path;

void solve(int v=0) {
  if(T1.cnt[v]) {
    reverse(all(path));
    for(int i=0; i<T1.cnt[v]; i++)
      T2.insert(path);
    reverse(all(path));
  }
  for(auto x : Q[stt[v]])
    ans[x.Y.Y] += x.Y.X*T2.get(x.X);
  for(int i=0; i<4; i++)
    if(T1.ch[i][v]) {
      path.pb(O_[i]);
      solve(T1.ch[i][v]);
      path.pop_back();
    }
}

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  O_[0]='A'; O_[O['C'] = 1]='C'; O_[O['G'] = 2]='G'; O_[O['U'] = 3]='U';
  
  cin >> n >> m;
  string s;
  T1.new_vertex();
  for(int i=0; i<n; i++) {
    cin >> s;
    T1.insert(s);
  }
  init_trie();
  string p, q;
  for(int i=0; i<m; i++) {
    cin >> p >> q;
    add(p, q, i);
  }
  T2.new_vertex();
  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