Submission #1069794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069794		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	59 ms	279332 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
 long long cur=0;

struct node{
    long long exist,cnt,child[4][4];
}nodes[2*1000010];
long long new_node(){
    cur++;
    memset(nodes[cur].child,-1,sizeof(nodes[cur].child));
    nodes[cur].exist=nodes[cur].cnt=0;
    return cur;
}
void add_string(string s){
    long long pos=0,len=s.size();
    for (long long i=0;i<len;i++){
        long long c=s[i]-'a',c2=s[len-i-1]-'a';
        if (nodes[pos].child[c][c2]==-1) nodes[pos].child[c][c2]=new_node();
        pos=nodes[pos].child[c][c2];
        nodes[pos].cnt++;
    }
    nodes[pos].exist++;
}
 long long n,m,i;
 string s,s1,s2;
string encode(string s){
    for (long long i=0;i<s.size();i++){
        if (s[i]=='C') s[i]='a';
        else if (s[i]=='U') s[i]='b';
        else if (s[i]=='G') s[i]='c';
        else if (s[i]=='A') s[i]='d';
    }
    return s;
}
long long query(string &s1,string &s2){
    long long pos=0,len=min(s1.size(),s2.size()),res,i;
    for (i=0;i<len;i++){
        long long c1=s1[i]-'a',c2=s2[i]-'a';
        if (nodes[pos].child[c1][c2]==-1) return 0;
        pos=nodes[pos].child[c1][c2];
    }
    res=nodes[pos].cnt;
    if (s1.size()>s2.size()){
        for (i=0;i<3;i++)
            if (nodes[pos].child[i][s2[len-1]-'a']!=-1){
                long long y=nodes[pos].child[i][s2[len-1]-'a'];
                res+=nodes[y].cnt;
            }
    }
    else if (s1.size()<s2.size()){
        for (i=0;i<3;i++)
            if (nodes[pos].child[s1[len-1]-'a'][i]!=-1){
                long long y=nodes[pos].child[s1[len-1]-'a'][i];
                res+=nodes[y].cnt;
            }
    }
    return res;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    memset(nodes[0].child,-1,sizeof(nodes[0].child));
    nodes[0].exist=nodes[0].cnt=0;
    cin>>n>>m;
    for (i=1;i<=n;i++){
        cin>>s;
        //cout<<encode(s)<<"\n";
        add_string(encode(s));
    }
    //cout<<"\n";
    while (m--){
        cin>>s1>>s2;
        s1=encode(s1);s2=encode(s2);
        reverse(s2.begin(),s2.end());
        //cout<<s1<<" "<<s2<<"\n";
        cout<<query(s1,s2)<<"\n";
    }

}

Compilation message (stderr)

selling_rna.cpp: In function 'std::string encode(std::string)':
selling_rna.cpp:27:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (long long i=0;i<s.size();i++){
      |                        ~^~~~~~~~~

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