oj.uz

Submission #853602

# Submission time Handle Problem Language Result Execution time Memory
853602 2023-09-24T17:40:29 Z epicci23 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 777 ms 1048576 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 777 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2512 KB Output is correct
2 Correct 14 ms 5332 KB Output is correct
3 Correct 15 ms 4044 KB Output is correct
4 Correct 10 ms 2516 KB Output is correct
5 Correct 14 ms 5328 KB Output is correct
6 Correct 15 ms 4304 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Runtime error 777 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -