Submission #1129600

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

selling_rna

#include <bits/stdc++.h>
using namespace std;
struct Trie {
    struct node{
      node* child[26][26];
      int cnt;
      node() {
        for(int i=0;i<26;i++) for(int j=0;j<26;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=s[i]-'A',c2=s[n-i-1]-'A';
        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[s[i]-'A'][v[i]-'A']==NULL) return 0;
        u=u->child[s[i]-'A'][v[i]-'A'];
      }
      head=u->cnt;
      queue<node*> q;q.push(u);
      if(n<m) {
        for(int i=n;i<m;i++) {
          int c=v[i]-'A',sz=q.size();
          for(int j=0;j<sz;j++) {
            node* top=q.front();q.pop();
            for(int k=0;k<26;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=s[i]-'A',sz=q.size();
          for(int j=0;j<sz;j++) {
            node* top=q.front();q.pop();
            for(int k=0;k<26;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