Submission #1129603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129603		halogenbr	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1604 ms	277152 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
int getNum(char f) {
  if(f=='A') return 0;
  if(f=='U') return 1;
  if(f=='G') return 2;
  return 3;
}
struct Trie {
    struct node{
      node* child[4][4];
      int cnt;
      node() {
        for(int i=0;i<4;i++) for(int j=0;j<4;j++) child[i][j]=NULL;
        cnt=0;
      }
    };
    node* root;
    Trie() {
      root=new node();
    }
    void add(string s) {
      node* u=root;
      int n=s.size();
      for(int i=0;i<n;i++) {
        int c1=getNum(s[i]),c2=getNum(s[n-i-1]);
        if(u->child[c1][c2]==NULL) u->child[c1][c2]=new node();
        u=u->child[c1][c2];
        u->cnt++;
      }
    }
    int solve(string s,string v) {
      node* u=root;
      int n=s.size(),m=v.size();
      int len=min(n,m),head=0,tail=INT_MAX;
      reverse(v.begin(),v.end());
      for(int i=0;i<len;i++) {
        if(u->child[getNum(s[i])][getNum(v[i])]==NULL) return 0;
        u=u->child[getNum(s[i])][getNum(v[i])];
      }
      head=u->cnt;
      queue<node*> q;q.push(u);
      if(n<m) {
        for(int i=n;i<m;i++) {
          int c=getNum(v[i]),sz=q.size();
          for(int j=0;j<sz;j++) {
            node* top=q.front();q.pop();
            for(int k=0;k<4;k++) if(top->child[k][c]!=NULL) q.push(top->child[k][c]);
          }
        }
      }else if(n>m) {
        for(int i=m;i<n;i++) {
          int c=getNum(s[i]),sz=q.size();
          for(int j=0;j<sz;j++) {
            node* top=q.front();q.pop();
            for(int k=0;k<4;k++) if(top->child[c][k]!=NULL) q.push(top->child[c][k]);
          }
        }
      } else return head;
      if(q.empty()) return 0;
      tail=0;
      while(!q.empty()) {
        node* top=q.front();q.pop();
        tail+=top->cnt;
      }
      return min(head,tail);
    }
  };
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    Trie trie;
    int n,m;cin>>n>>m;
    while(n--) {
      string x;cin>>x;
      trie.add(x);
    }
    while(m--) {
      string u,v;cin>>u>>v;
      cout << trie.solve(u,v)<<'\n';
    }
    return 0;
}

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