Submission #1079049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079049		alexander707070	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1579 ms	165740 KiB

selling_rna

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

struct node{
    vector<int> words;
    int ch[4];
};

int n,m;
string word[MAXN],s,t;

node prefix[2000007],suffix[2000007];
int pr,sf;

void transform(string &s){
    for(int f=0;f<s.size();f++){
        if(s[f]=='G')s[f]='B';
        if(s[f]=='U')s[f]='D';
    }
}

void add(string s,int id){
    int curr=0;
    for(int i=0;i<s.size();i++){
        if(prefix[curr].ch[s[i]-'A']==0){
            pr++; prefix[curr].ch[s[i]-'A']=pr;
        }

        curr=prefix[curr].ch[s[i]-'A'];
    }

    prefix[curr].words.push_back(id);

    reverse(s.begin(),s.end());

    curr=0;
    for(int i=0;i<s.size();i++){
        if(suffix[curr].ch[s[i]-'A']==0){
            sf++; suffix[curr].ch[s[i]-'A']=sf;
        }

        curr=suffix[curr].ch[s[i]-'A'];
    }

    suffix[curr].words.push_back(id);
}

int li[MAXN],tim,ans;

void dfs(int x){
    for(int i:prefix[x].words)li[i]=tim;

    for(int i=0;i<4;i++){
        if(prefix[x].ch[i]!=0)dfs(prefix[x].ch[i]);
    }
}

void check(string s){
    tim++;

    int curr=0;
    for(int i=0;i<s.size();i++){
        if(prefix[curr].ch[s[i]-'A']==0)return;
        curr=prefix[curr].ch[s[i]-'A'];
    }
    
    dfs(curr);
}

void dfs2(int x){
    for(int i:suffix[x].words){
        if(li[i]==tim)ans++;
    }

    for(int i=0;i<4;i++){
        if(suffix[x].ch[i]!=0)dfs2(suffix[x].ch[i]);
    }
}

void query(string s){
    reverse(s.begin(),s.end());

    int curr=0;
    for(int i=0;i<s.size();i++){
        if(suffix[curr].ch[s[i]-'A']==0)return;
        curr=suffix[curr].ch[s[i]-'A'];
    }

    dfs2(curr);
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>word[i];

        transform(word[i]);

        add(word[i],i);
    }

    for(int i=1;i<=m;i++){
        cin>>s>>t;

        transform(s);
        transform(t);

        ans=0;
        check(s);
        query(t);

        cout<<ans<<"\n";
    }

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void transform(std::string&)':
selling_rna.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int f=0;f<s.size();f++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'void add(std::string, int)':
selling_rna.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'void check(std::string)':
selling_rna.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'void query(std::string)':
selling_rna.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

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