oj.uz

Submission #1079049

# Submission time Handle Problem Language Result Execution time Memory
1079049 2024-08-28T09:58:21 Z alexander707070 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 165740 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 160124 KB Output is correct
2 Correct 63 ms 160084 KB Output is correct
3 Correct 63 ms 160084 KB Output is correct
4 Correct 67 ms 160084 KB Output is correct
5 Correct 66 ms 160128 KB Output is correct
6 Correct 69 ms 160080 KB Output is correct
7 Correct 70 ms 160080 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1579 ms 165740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1042 ms 161628 KB Output is correct
2 Correct 578 ms 160844 KB Output is correct
3 Correct 684 ms 161284 KB Output is correct
4 Correct 307 ms 161104 KB Output is correct
5 Correct 648 ms 161100 KB Output is correct
6 Correct 836 ms 161360 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 160124 KB Output is correct
2 Correct 63 ms 160084 KB Output is correct
3 Correct 63 ms 160084 KB Output is correct
4 Correct 67 ms 160084 KB Output is correct
5 Correct 66 ms 160128 KB Output is correct
6 Correct 69 ms 160080 KB Output is correct
7 Correct 70 ms 160080 KB Output is correct
8 Execution timed out 1579 ms 165740 KB Time limit exceeded
9 Halted 0 ms 0 KB -