oj.uz

Submission #933050

# Submission time Handle Problem Language Result Execution time Memory
933050 2024-02-24T23:37:15 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 907 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define deb(x) ;
using lli=long long int;
 
 
#ifndef LOCAL
    #define endl '\n'
#endif
 
struct Node{
  map<pair<char,char>, lli> next;
  lli cant=0;
};
vector<Node> trie;
lli currNode=0;
lli newNode(){
  trie.pb(Node());
  return currNode++;
}

void addword(string s, bool b,lli ind, lli pt){
  for(lli i=ind; i<s.size(); ++i){
    if(b){
    if(trie[pt].next.find({s[i], 0})==trie[pt].next.end()){
      trie[pt].next[{s[i], 0}]=newNode();
    }
    pt=trie[pt].next[{s[i],0}];
    trie[pt].cant++;
    }
    else{
       if(trie[pt].next.find({0,s[i]})==trie[pt].next.end()){
      trie[pt].next[{0,s[i]}]=newNode();
    }
    pt=trie[pt].next[{0,s[i]}];
    trie[pt].cant++;
    }
  }
}

void add(string s){
  lli pt=0;

  string r=s;
  reverse(r.begin(), r.end());
  for(lli i=0; i<s.size(); ++i){
    deb(i);
    trie[pt].cant++;
    if(trie[pt].next.find({s[i], r[i]})==trie[pt].next.end()){
      trie[pt].next[{s[i], r[i]}]=newNode();
    }
    addword(s, 1, i, pt);
    addword(r, 0, i, pt);
    pt=trie[pt].next[{s[i], r[i]}];

  }
  trie[pt].cant++;
}


lli query(string &p, string &q, lli ind, lli pt){
  deb(p);
  deb(q);
  deb(ind);
  deb(pt);
  if(p.size()<=ind){
    if(q.size()<=ind){
      return trie[pt].cant;
    }
    else{
      if(ind==q.size()){
        return trie[pt].cant;
      }
      lli ans=0;
      if(trie[pt].next.find({0, q[ind]})!=trie[pt].next.end()){
      ans+=query(p,q, ind+1, trie[pt].next[{0, q[ind]}]);
      }
  
      return ans;
    }
  }
  else{
    if(q.size()<=ind){
         if(ind==p.size()){
        return trie[pt].cant;
      }
      lli ans=0;
      if(trie[pt].next.find({p[ind],0})!=trie[pt].next.end()){
      ans+=query(p,q, ind+1, trie[pt].next[{p[ind],0}]);
      }
  
      return ans;
    }
    else{
      if(ind==p.size() && ind==q.size()){
        return trie[pt].cant;
      }
      lli ans=0;
      if(trie[pt].next.find({p[ind],q[ind] })!=trie[pt].next.end()){
        ans+=query(p,q,ind+1, trie[pt].next[{p[ind], q[ind]}]);
      }
      return ans;
    }
  }
}

void solve(){
    lli n;
    lli m;
    cin>>n>>m;
    newNode();
    deb(n);
    for(lli i=0; i<n; ++i){
      deb(i);
      string s;
      cin>>s;
      deb(s);
      add(s);
    }
    for(lli i=0; i<m; ++i){
      string p,q;
      cin>>p>>q;
      reverse(q.begin(), q.end());
      lli ans=query(p,q,0,0);
      cout<<ans<<endl;
    }

}
 
 
int main(){
  ios::ios_base::sync_with_stdio(0);
  cin.tie(0);
  #ifdef LOCAL
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);
  #endif
  lli t=1;
//  cin>>t;
  while(t--){
    
    solve();

  }
}

Compilation message

selling_rna.cpp: In function 'void addword(std::string, bool, lli, lli)':
selling_rna.cpp:24:19: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(lli i=ind; i<s.size(); ++i){
      |                  ~^~~~~~~~~
selling_rna.cpp: In function 'void add(std::string)':
selling_rna.cpp:47:17: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(lli i=0; i<s.size(); ++i){
      |                ~^~~~~~~~~
selling_rna.cpp: In function 'lli query(std::string&, std::string&, lli, lli)':
selling_rna.cpp:67:14: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'lli' {aka 'long long int'} [-Wsign-compare]
   67 |   if(p.size()<=ind){
      |      ~~~~~~~~^~~~~
selling_rna.cpp:68:16: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'lli' {aka 'long long int'} [-Wsign-compare]
   68 |     if(q.size()<=ind){
      |        ~~~~~~~~^~~~~
selling_rna.cpp:72:13: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |       if(ind==q.size()){
      |          ~~~^~~~~~~~~~
selling_rna.cpp:84:16: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'lli' {aka 'long long int'} [-Wsign-compare]
   84 |     if(q.size()<=ind){
      |        ~~~~~~~~^~~~~
selling_rna.cpp:85:16: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |          if(ind==p.size()){
      |             ~~~^~~~~~~~~~
selling_rna.cpp:96:13: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |       if(ind==p.size() && ind==q.size()){
      |          ~~~^~~~~~~~~~
selling_rna.cpp:96:30: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |       if(ind==p.size() && ind==q.size()){
      |                           ~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 907 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1104 KB Output is correct
2 Correct 38 ms 8220 KB Output is correct
3 Correct 34 ms 4200 KB Output is correct
4 Correct 19 ms 852 KB Output is correct
5 Correct 38 ms 7964 KB Output is correct
6 Correct 34 ms 4280 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Runtime error 907 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -