Submission #1279349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279349		escobrand	Selling RNA Strands (JOI16_selling_rna)	C++20	0 / 100	222 ms	171672 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;
#define fi first
#define se second
#define ll long long
#define all(v) v.begin(),v.end()
#define mk make_pair
#define pb push_back
#define eb emplace_back
typedef pair<int,int> pii;

int id[300];

const int maxn = 1e5 + 10;
int t;
bitset<maxn> bit[maxn];

struct Trie
{
  struct Node
  {
    int child[4];
    int idx;
    vector<int> v;
    
    Node()
    {
      idx = 0;
      for(int i = 0;i<4;i++)child[i] = -1;
    }
  };
  vector<Node> nodes;
  
  int create()
  {
    nodes.eb();
    return nodes.size()-1;
  }
  
  Trie()
  {
    create();
  }
  
  void add(string &s ,int idx)
  {
    int pos = 0;
    for(char ch : s)
    {
      int c = id[ch];
      if(nodes[pos].child[c]==-1)nodes[pos].child[c] = create();
      pos = nodes[pos].child[c];
      nodes[pos].v.eb(idx);
    }
    
  }
  
  int cal(string &s)
  {
    int pos = 0;
    for(char ch : s)
    {
      int c = id[ch];
      if(nodes[pos].child[c]==-1)return 0;
      pos = nodes[pos].child[c];
    }
    if(nodes[pos].idx==0)
    {
      nodes[pos].idx = ++t;
      for(const int & k : nodes[pos].v) bit[t].set(k);
    }
    return nodes[pos].idx;
  }
}pre,suf;

int n,m;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    id['A'] = 0;
    id['U'] = 1;
    id['G'] = 2;
    id['C'] = 3;
    cin>>n>>m;
    for(int i = 0;i<n;i++)
    {
      string s;
      cin>>s;
      pre.add(s,i);
      reverse(all(s));
      suf.add(s,i);
    }
    
    while(m--)
    {
      string p,s;
      cin>>p>>s;
      int i = pre.cal(p);
      int j = suf.cal(s);
      if(i&&j)
      {
        cout<<(bit[i]&bit[j]).count()<<'\n';
      }
      else cout<<0<<'\n';
    }
    
    return 0;
}

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