Submission #853602

#	Time	Username	Problem	Language	Result	Execution time	Memory
853602		epicci23	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	777 ms	1048576 KiB

selling_rna

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

struct Node{
  int ans;
  array<Node*,4> kids;
  Node* sub;
  Node(){ans=0;kids={NULL,NULL,NULL,NULL};sub=NULL;}
};

constexpr int BL = 1000;

void add(string &s,Node* rt,int p){
  if(rt==NULL) return;
  if(p>BL) return;
  int hm=sz(s);
  if(p+1<hm){
  if(s[p+1]=='A'){
  	if(rt->kids[0]==NULL) rt->kids[0] = new Node();
    add(s,rt->kids[0],p+1);
  }
  else if(s[p+1]=='G'){
  	if(rt->kids[1]==NULL) rt->kids[1] = new Node();
    add(s,rt->kids[1],p+1);
  }
  else if(s[p+1]=='C'){
  	if(rt->kids[2]==NULL) rt->kids[2] = new Node();
    add(s,rt->kids[2],p+1);
  }
  else{
  	if(rt->kids[3]==NULL) rt->kids[3] = new Node();
    add(s,rt->kids[3],p+1);
  }
 }
  if(rt->sub==NULL) rt->sub=new Node();
  Node* c = rt->sub;
  for(int x=hm-1;x>=0 && hm-x<=BL;x--){
	 if(s[x]=='A'){
	  	if(c->kids[0]==NULL) c->kids[0] = new Node();
	    c=c->kids[0];
	  }
	 else if(s[x]=='G'){
	  	if(c->kids[1]==NULL) c->kids[1] = new Node();
	    c=c->kids[1];
	  }
	 else if(s[x]=='C'){
	  	if(c->kids[2]==NULL) c->kids[2] = new Node();
	    c=c->kids[2];
	  }
	 else{
	  	if(c->kids[3]==NULL) c->kids[3] = new Node();
	    c=c->kids[3];
	 }
    c->ans++;
    //cout << p << " " << x << " : " << c->ans << endl;
  }
}

int query(Node* rt,int p,string &s){
  if(rt==NULL) return 0;
  if(p+1==sz(s)) return rt->ans;
  if(s[p+1]=='A') return query(rt->kids[0],p+1,s);
  else if(s[p+1]=='G') return query(rt->kids[1],p+1,s);
  else if(s[p+1]=='C') return query(rt->kids[2],p+1,s);
  return query(rt->kids[3],p+1,s);
}



void solve(){
  int n,m;
  cin >> n >> m;
  vector<string> v;
  
  Node *rt=new Node();

  for(int i=1;i<=n;i++){
    string s; cin >> s;
    v.pb(s);
    add(s,rt,-1);
  }

  while(m--){
  	string s1,s2;
  	cin >> s1 >> s2;
    if(sz(s1)+sz(s2)>=BL){
      int cur=0;
      for(int i=0;i<n;i++){
      	bool ok=1;
      	if(sz(s1)>sz(v[i]) || sz(s2)>sz(v[i])) continue;
        for(int j=0;j<sz(s1);j++) if(s1[j]!=v[i][j]) ok=0;
        int lol=0;
        for(int j=sz(v[i])-sz(s2);j<sz(v[i]);j++) if(v[i][j]!=s2[lol++]) ok=0;
        if(ok) cur++;
      }
      cout << cur << endl;
    }
    else{
      Node* p=rt;
      bool noo=0;
      for(int i=0;i<sz(s1);i++){
      	if(p==NULL){
      	  noo=1;
      	  break;
      	}
        if(s1[i]=='A') p=p->kids[0];
        else if(s1[i]=='G') p=p->kids[1];
        else if(s1[i]=='C') p=p->kids[2];
        else p=p->kids[3];
      }
      if(noo || p==NULL){
      	cout << 0 << endl;
      	continue;
      }
      reverse(all(s2));
      p=p->sub;
      cout << query(p,-1,s2) << endl;
    }  
  }
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

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